Телекоммуникационные технологии


Элементы теории графов - часть 2


Неориентированный граф G = <V,E> называется связанным, если для любых двух узлов x,y О V существует последовательность ребер из набора E, соединяющий x и y.

Граф 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, а сами графы изоморфны.




Начало  Назад  Вперед



Книжный магазин