и только тогда, когда множество

Граф G связан тогда и только тогда, когда множество его вершин нельзя разбить на два непустых подмножества V1 и V2 так, чтобы обе граничные точки каждого ребра находились в одном и том же подмножестве.

Граф G называется k-связным (k і 1), если не существует набора из k-1 или меньшего числа узлов V`Н V, такого, что удаление всех узлов V` и сопряженных с ними ребер, сделают граф G несвязанным.

Теорема Менгера

: граф G является k-связанным тогда и только тогда, когда любые два различные узла x и y графа G соединены по крайне мере k путями, не содержащими общих узлов.

k-связанные графы представляют особый интерес для сетевых приложений. Определенную проблему составляет автоматическое отображение графа на экране или бумаге. Кроме того, для многих приложений (например, CAD) все узлы графа должны совпадать с узлами технологической сетки. Возникают и другие ограничения, например необходимость размещения всех узлов на прямой линии. В этом случае ребра графа могут представлять собой кривые линии, дуги или ломаные линии, состоящие из отрезков прямых. Смотри, например, рисунок 10.21.2.



Рис. 10.21.2

Граф слева безусловно легче воспринять, чем граф справа, хотя они эквивалентны. Существует ряд алгоритмов, позволяющих определить, является ли граф плоским. Так граф на рис. 10.21.3 на первый взгляд не является плоским (ведь его ребра пересекаются в нескольких местах). Но он может быть перерисован (см. рис. 10.21.3а), после чего его плоскостность уже не подвергается сомнению.









1





2





3





4





5







1





0





0





1





1





0







2





0





0





0





1





1







3





1





0





0





0





1







4





1





1





0





0





0







5





0





1





1





0





0





Матрица смежности графа G



Рис. 10.21.3. Граф и его матрица смежности



Рис. 10.21.3а. Преобразование графа с рис 3

Матрица смежности, характеризующая этот граф, эквивалентна приведенной на рис. 10.21.3, а сами графы изоморфны. Для представления графа может использоваться Булева функция S(x,y), для которой S(i,j)=1 тогда и только тогда, когда (i,j)О E. S(i,j) обозначает ребро графа, соединяющее узлы i и j. Одной из возможностей реализации s является использование матрицы смежности А графа g. А – двухмерная матрица.


Содержание  Назад  Вперед

---

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий

---