Опорный конспект № 38

6145
0
08 июля 2009
(38.) Представлены сведения о графах: основные понятия и способы задания графов, маршруты, цепи и циклы, некоторые классы графов.

38.1. Основные понятия и способы задания графов

 О: Граф38_html_62eb365e.gif- вершины,38_html_3633907f.gif,

38_html_m21150521.gifпредставляет собой ребра,38_html_76886e51.gifинцидентно38_html_5c952c00.gif

38_html_7a623d36.gifявляется ориентированным графом, в случае, когда38_html_m34912207.gif- упорядоченные пары из38_html_m2756962b.gif.

О: Мультиграфом называют граф, который предполагает наличие кратных ребер.

О: Степень вершины графа38_html_7a623d36.gifобозначает число ребер, инцидентных38_html_m45e2bcf6.gif.

Граф отображается в виде диаграммы или определяется матрицей смежности38_html_m160ca5a.gif38_html_6efbf575.gif-го порядка, в которой38_html_m702465c2.gifэквивалентно количеству ребер, инцидентных38_html_m4a8a5a88.gifдля неориентированного графа.

 

38.2. Маршруты, цепи и циклы

 О: Маршрут38_html_36b4ecae.gifв графе38_html_m6747afc0.gifпредполагает наличие у двух соседних ребер общей инцидентной вершины.

Цепь представляет собой маршрут38_html_36b4ecae.gif, у которого нет равных ребер. Простой цепью называют маршрут38_html_36b4ecae.gif, у которого все вершины, за исключением, может быть, первой и последней, различны.

Цикл есть цепь, которая предполагает совпадение начальной и конечной вершин.

О: Граф38_html_7a623d36.gifможно определить в качестве связного при условии, что любая пара его вершин может быть соединена цепью.

О: Эйлеров граф — это связный неориентированный мультиграф, для которого существует цикл, включающий в себя все ребра.

Т: Связный неориентированный мультиграф эйлеров т. и т.т. при четности степени его вершин.

 

38.3. Некоторые классы графов

 О: Дерево представляет связной граф, который предполагает отсутствие циклов, лесом называют несвязанный граф без циклов.

Всякая цепь в таком графе является простой. Любые две вершины дерева связаны лишь одной цепью.

О: В качестве остова графа38_html_m11de5e45.gifопределяют дерево38_html_4acedaba.gif

О: Двудольный граф38_html_73b8422.gifпри этом для каждого ребра характерно наличие одного конца из38_html_m760e0f46.gif, другого — из38_html_m36d618d.gif.



(38.4.) Сформулируем понятие конечного автомата, обозначим входной алфавит, выходной алфавит, алфавит состояний, функцию переходов, функцию выходов, на рисунке изобразим граф переходов.
2463 0
(38.3.) Большинство графов, которые используются в приложениях (например, графы сортировок, классификаций) предполагают наличие диаграмм, именуемых деревьями. Связный неориентированный граф без циклов, в частности, предполагающий отсутствие петель и кратных ребер, именуют деревом. Несвязный неориентированный граф без цикла — лес, его связные компоненты являются деревьями.
7208 0
(38.2.) В рамках обозначенной темы рассмотрим случай определения связного неориентированного мультиграфа в качестве эйлерова и гамильтонова графа.
8987 0

    Вы должны авторизоваться, чтобы оставлять комментарии.

    Радиомастер
    © 2005–2013 radiomaster.ru
    admin@radiomaster.ru
    При использовании материалов данного сайта прямая и явная ссылка на сайт radiomaster.ru обязательна. 0.7264 s