Элементы теории графов
Семёнов Ю.А. (ГНЦ ИТЭФ), book.itep.ru
Графы представляют собой наиболее абстрактную структуру, с которой приходится сталкиваться в теории ЭВМ (computer science). Графы используются для описания алгоритмов автоматического проектирования, в диаграммах машины конечных состояний, при решении задач маршрутизации потоков и т.д. Любая система, предполагающая наличие дискретных состояний или наличие узлов и переходов между ними может быть описана графом. Соединения между узлами графа называются ребрами. Если узлы графа не нумерованы, то ребра являются неориентированными. У графа с нумерованными узлами ребра ориентированы. Ребрам могут быть присвоены определенные веса или метки. На рис. 10.21.1А и 10.21.1Б приведены примеры обычного и ориентированного графа.
Рис. 10.21.1 Примеры неориентированного и ориентированного графов (А и Б)
Введем более строгие определения. Граф представляет собой структуру П = <V,E>, в которой V представляет собой конечный набор узлов, а EН VЕV представляет собой конечный набор ребер. Для ориентированного графа E Н Vґ V - конечный набор ориентированных ребер. Ребром может быть прямая или кривая линия. Ребра не могут иметь общих точек кроме вершин (узлов) графа. Замкнутая кривая в E может иметь только одну точку из множества V, а каждая незамкнутая кривая в E имеет ровно две точки множества V. Если V и E конечные множества, то и граф им соответствующий называется конечным. Граф называется вырожденным, если он не имеет ребер. Параллельными ребрами графа называются такие, которые имеют общие узлы начала и конца.
Графы отображаются на плоскости набором точек и соединяющих их линий или векторов. При этом грани могут отображаться и кривыми линиями, а их длина не играет никакой роли.
Граф G называется плоским, если его можно отобразить в плоскости без пересечения его граней.
Очертанием графа (face) считается любая топологически связанная область, ограниченная ребрами графа.
Неориентированный граф 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 |
Рис. 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.
А - двухмерная матрица.
Для описания графа с помощью матрицы смежности A(i,j), где (i,j) О E, необходимо пронумеровать узлы графа. Элементы матрицы могут принимать значения 0 или 1. Так как представленный на рисунке граф не имеет ребер исходящих и завершающихся в одном и том же узле (нет петель), диагональные элементы матрицы равны нулю. Единицы присутствуют в позициях, которые соответствуют парам узлов, соединенных ребрами, например, 1-3, 1-4 или 5-2 и 5-3. Число ребер, исходящих из вершины (петля учитывается дважды), называется степенью вершины d(v). В конечном графе число вершин с нечетной степенью всегда четно.
Другой способ представления графа обеспечивает функция, которая выдает списки узлов, с которыми данный узел связан непосредственно. Для графа, отображенного на рис. 10.21.4, такое описание можно представить в виде структуры (таблица 10.21.1). В колонке s представлены номера узлов, далее в строке таблицы следует список соседних узлов. По этой причине число колонок в каждой из строк различно.
Рис. 10.21.4
Таблица 10.21.1.
| S | Список "соседних" узлов | |||
| 1 | 2 | 5 | 6 | |
| 2 | 1 | 3 | ||
| 3 | 2 | 4 | 5 | |
| 4 | 3 | |||
| 5 | 1 | 3 | 6 | 7 |
| 6 | 1 | 5 | 7 | |
| 7 | 5 | 6 | ||
Граф называется полным, если любые две вершины являются смежными.
Если для всех вершин d(v) = k, то граф называется однородным графом степени k или k-однородным. Граф на рис. 10.21.5 является полным и 3-однородным.
Рис. 10.21.5.
Конечная последовательность ребер графа e1, e2,…,en называется маршрутом длины n. Маршрут называется замкнутым, если вершины начала и конца маршрута совпадают. Если ребра, образующие маршрут различны, то такой маршрут называется цепью.
Граф называется деревом, если он связан и не имеет циклов. Граф является деревом тогда и только тогда, когда каждая пара различных вершин соединяется одной и только одной цепью.
Каждое дерево с n вершинами имеет ровно n- 1 ребро. Удаление любого ребра в дереве делает его несвязным. По этой причине дерево можно считать минимальным связным графом. Если все вершины графа G принадлежат дереву Т, то считается, что дерево покрывает граф G.
Граф, не имеющий циклов и состоящий из k компонент, называется лесом из k деревьев. Лес из k деревьев, содержащий n вершин имеет в точности n-k ребер.
Пусть G=(v,e) связный граф и FМ E подмножество его ребер. При этом F называется разделяющим подмножеством тогда и только тогда, когда подграф G'=(V, E-F) несвязан. E-F обозначает множество ребер, которое принадлежит Е, но не принадлежит F.
Если узлы графа могут быть соединены несколькими путями, сеть, описываемая таким графом, обладает повышенной надежностью. Рассмотрим задачу выбора оптимального дерева маршрутов, лишенного циклов, в такой сети (см. рис. 10.21.6). Алгоритм используется в схеме "расширяющееся дерево" для локальных сетей со сложной топологией. Алгоритм преобразует многосвязный граф в плоский без замкнутых структур.
Рис. 10.21.6.
В качестве начального выбираем узел 1. Матрица оценки формируется поэтапно (А-E). На этапе А выбирается узел 5, так как к нему ведет ребро с метрикой 1. Здесь становятся доступными ребра, ведущие к узлам 2, 4, 6 и 7. Ребро 1-5 из рассмотрения устраняется. На следующем этапе выбирается узел 7, к нему от узла 5 ведет ребро с метрикой 1. Здесь в рассмотрение включаются ребра 7-4 и 7-8. Следующим выбранным узлом становится 4 и включается в перечень ребро 4-2. Далее рассматривается узел 6 и ребра 6-8 и 6-3.
В результате граф приобретает вид, показанный на рисунке 10.21.7.
Рис. 10.21.7.
Рассмотренный алгоритм сходен с алгоритмом Дикстры, используемым для поиска наилучшего пути во внутреннем протоколе маршрутизации ospf.
Выбранный метод аналитического представления графа достаточно прост, но требует для графа с N узлами N2 ячеек памяти (бит). Впрочем, для неориентированного графа матрица является симметричной и для ее хранения в памяти ЭВМ достаточно N(N-1)/2 ячеек.Это справедливо и для ориентированных графов без петель.
Петлей называется ребро графа, которое начинается и завершается в одном и том же узле (рис. 10.21.8).
Рис. 10.21.8.
Справедливо следующее утверждение. Узлы i,j соединены путем длиной k тогда и только тогда, когда Ak(i,j)=1.
Надо сказать, что графы являются весьма удобным средством описания и оптимизации алгоритмов вычисления. В качестве примера рассмотрим вычисление квадратного полинома ax2+bx+c по схеме Горнера (рис. 10.21.9).
Рис. 10.21.9. Граф вычисления квадратного полинома по схеме Горнера.
