Представление графов

Графы

Введение в теорию графов

Ориентированный граф (directed graph)определяется как пара (V,Е), где
конечное множество, а Е бинарное отношение на V, т. е. подмножество
множества VV. Ориентированный граф иногда для краткости называют ор-
графом (digraph). Множество V называют множеством вершин графа (vertex
set); его элемент называют вершиной графа (vertex; множественное число ver-
tices). Множество Е называют множеством рёбер (edge set) графа; его элемен-
ты называют рёбрами (edges). На рис. 5.1(a) показан ориентированный граф
с множеством вершин {1,2,3,4,5,6}. Вершины изображены кружками, а рёб-
ра стрелками. Заметим, что граф может содержать рёбра-циклы (self-loops),
соединяющие вершину с собой.

В неориентированном (undirected) графе G = (V, Е) множество рёбер Е
состоит из неупорядоченных (unordered) пар вершин: парами являются множе-
ства { и, v }, где u, v V и . Мы будем обозначать неориентированное ребро
как (u, v) вместо { u, v }; при этом для неориентированного графа (u, v) и (v, u)
обозначают одно и то же ребро. Неориентированный граф не может содержать
рёбер-циклов, и каждое ребро состоит из двух различных вершин («соединяя»
их). На рисунке 5.1(б) изображён неориентированный граф с множеством вер-
шин {1,2,3,4,5,6}.

Многие понятия параллельно определяются для ориентированных и неори-
ентированных графов (с соответствующими изменениями). Про ребро (и, v)
ориентированного графа говорят, что оно выходит из (incident from, leaves)
вершины и и входит (incident to, enters) в вершину v.

Рисунок 5.1 – Ориентированные и неориентированные графы

На рисунке 5.1 изображены: (а) Ориентированный граф (V, Е), где V = {1,2,3,4,5,6} и Е = {(1,2),(2,2),(2,4),(2,5),(4,1),(4,5),(5,4),
(6,3)}. Ребро (2,2) является ребром-циклом. (б) Неориентированный граф G = (V, Е), где
V = {1,2,3,4,5,6} и Е = {(1,2), (1,5), (2,5), (3,6)}. Вершина 4 является изолированной (не
имеет смежных вершин). (в) Подграф графа (а), получающийся его ограничением на мно-
жество вершин {1,2,3,6}.

Например, на рис. 5.1(а) имеется три ребра, выходящих из вершины 2 (рёбра (2,2), (2,4), (2,5)) и два
ребра, в неё входящих (рёбра (1,2), (2,2)). Про ребро (u, v) неориентированно-
го графа говорят, что оно инцидентно вершинам (incident on vertices) и и v.
Например, на рис. 5.1(б) есть два ребра, инцидентные вершине 2 (рёбра (1,2) и
(2, 5)).

Если в графе G имеется ребро (u, v), говорят, что вершина v смежна с вер-
шиной и (is adjacent tо u). Для неориентированных графов отношение смежности
является симметричным, но для ориентированных графов это не обязательно.
Если вершина v смежна с вершиной и в ориентированном графе, пишут и v.
Для обоих рисунков 5.1(а) и 5.1(б) вершина 2 является смежной с вершиной 1,
но лишь во втором из них вершина 1 смежна с вершиной 2 (в первом случае
ребро (2, 1) отсутствует в графе).

Степенью (degree) вершины в неориентированном графе называется чис-
ло инцидентных ей рёбер. Например, для графа на рис. 5.1(б) степень верши-
ны 2 равна 2. Для ориентированного графа различают исходящую степень (out-
degree), определяемую как число выходящих из неё рёбер, и входящую степень
(in-degree), определяемую как число входящих в неё рёбер. Сумма исходящей
и входящей степеней называется степенью (degree) вершины. Например, верши-
на 2 в графе на рис. 5.1(а) имеет входящую степень 2, исходящую степень 3 и
степень 5.

Путь длины k (path of length k) из вершины, u в вершину v определяется
как последовательность вершин , в которой ,и
для всех i = 1,2,...,k. Таким образом, путь длины k состоит из
k рёбер. Этот путь содержит (contains) вершины и рёбра . Вершину называют началом пути, вершину - его кон-
цом; говорят, что путь ведёт из в (from to ). Если для данных вершин
и и и' существует путь р из и в и', то говорят, что вершина и' достижима
из и по пути р (u ' is reachable from и via р). В этом случае мы пишем (для
ориентированных графов) .

Путь называется простым (simple), если все вершины в нём различны.
Например, на рис. 5.1(а) есть простой путь длины 3, а также путь
той же длины, не являющийся простым.

Подпуть (subpath) пути р = получится, если мы возьмём не-
которое количество идущих подряд вершин этого пути, т.е. последовательность
при некоторых i, j, для которых 0 i j k.

Циклом (cycle) в ориентированном графе называется путь, в котором на-
чальная вершина совпадает с конечной и который содержит хотя бы одно ребро.
Циклназывается простым (simple), если в нём нет одинаковых
вершин (кроме первой и последней), т.е. если все вершины различны.
Ребро-цикл является циклом длины 1. Мы отождествляем циклы, отличающиеся
сдвигом вдоль цикла: один и тот же цикл длины k может быть представлен k
различными путями (в качестве начала и конца можно взять любую из k
вершин). Например, на рис. 5.1(а) пути , и пред-
ставляют один и тот же цикл. Этот цикл является простым, в то время как цикл таковым не является. На том же рисунке есть цикл ,
образованный единственным ребром-циклом (2,2). Ориентированный граф, не
содержащий рёбер-циклов, называется простым (simple).

В неориентированном графе путь называется (простым) цик-
лом, если k 3, и все вершины различны. Например, на
рис. 5.1(б) имеется простой цикл .

Граф, в котором нет циклов, называется ациклическим (acyclic).

Неориентированный граф называется связным (connected), если для любой
пары вершин существует путь из одной в другую. Для неориентированного
графа отношение «быть достижимым из» является отношением эквивалентности
на множестве вершин. Классы эквивалентности называются связными компо-
нентами (connected components) графа. Например, на рис. 5.1(б) имеются три
связные компоненты: {l, 2, 5}, {3, 6} и {4}. Неориентированный граф связен
тогда и только тогда, когда он состоит из единственной связной компоненты.

Ориентированный граф называется сильно связным (strongly connected), ес-
ли из любой его вершины достижима (по ориентированным путям) любая другая.
Любой ориентированный граф можно разбить на сильно связные компоненты
(strongly connected components), которые определяются как классы эквивалент-
ности отношения «и достижимо из v и v достижимо из и». Ориентированный
граф сильно связен тогда и только тогда, когда состоит из единственной сильно
связной компоненты. Граф на рис. 5.1(а) имеет три таких компоненты: {1, 2, 4, 5},
{3} и {6}. Заметим, что вершины {3,6} не входят в одну сильно связную ком-
поненту, так как 3 достижима из 6, но не наоборот.

Два графа G = (V, Е) и G' = (V ', Е ’) называются изоморфными (isomor-
phic), если существует взаимно однозначное соответствие f: между мно-
жествами их вершин, при котором рёбрам одного графа соответствуют рёбра
другого: (и, v) Е тогда и только тогда, когда (f (u), f (v)) Е'. Можно сказать,
что изоморфные графы - это один и тот же граф, в котором вершины названы
по-разному. На рис. 5.2(а) приведён пример двух изоморфных графов G и G ' с
множествами вершин V = {1,2,3,4,5,6} и V ' = { u,v,w,х,у,z }. Функция f: , для которой f (1) = и, f (2) = v, f (3) = w, f (4) = х, f (5) = у, f (6) = z, явля-
ется изоморфизмом. Напротив, графы на рис. 5.2(б) не изоморфны, хотя оба име-
ют по 5 вершин и по 7 рёбер. Чтобы убедиться, что они не изоморфны, достаточно отметить, что в верхнем графе есть вершина степени 4, а в нижнем - нет.

Граф G ' = (V ', Е')называют подграфом (subgraph) графа G = (V, Е), если
Е' Е и V ' V. Если в графе G = (V, Е)выбрать произвольное множество
вершин V ', то можно рассмотреть его подграф, состоящий из этих вершин и
всех соединяющих их рёбер, т.е. граф G ' = (V ', Е '), для которого

Этот подграф можно назвать ограничением графа G на множество вершин V '
(subgraph of G induced by U '). Ограничение графа рис. 5.1(а) на множество
вершин {1,2,3,6} показано на рис. 5.1(в) и имеет три ребра (1,2), (2,2), (6,3).

Для любого неориентированного графа G можно рассмотреть его ориенти-
рованный вариант (directed version), заменив каждое неориентированное ребро { u, v } на пару ориентированных рёбер (u, v) и (v, и), идущих в противоположных
направлениях. С другой стороны, для каждого ориентированного графа можно
рассмотреть его неориентированный вариант (undirected version), забыв про
ориентацию рёбер, удалив рёбра-циклы и соединив рёбра (u, v) и (v, u) в одно
неориентированное ребро { u, v }. В ориентированном графе соседом (neighbor)
вершины и называют любую вершину, соединённую с ней ребром (в ту или
другую сторону); таким образом, v является соседом и тогда и только тогда,
когда v смежно и или и смежно v. Для неориентированного графа выражения
«v - сосед и» и «v смежна с и» являются синонимами.

Рисунок 5.2 – Примеры изоморфных и неизоморфных графов

(а) Изоморфные графы. (б) Неизоморфные графы: верхний имеет вершину степени 4, а нижний – нет.

Некоторые виды графов имеют специальные названия. Полным (complete)
графом называют неориентированный граф, содержащий все возможные рёбра
для данного множества вершин (любая вершина смежна любой другой). Не-
ориентированный граф (V, E)называют двудольным (bipartite), если множество
вершин V можно разбить на две части V ₁ и V ₂ таким образом, что концы
любого ребра оказываются в разных частях. Ациклический неориентированный
граф называют лесом (forest), а связный ациклический неориентированный граф
называют деревом без выделенного корня (подробно деревья рассматриваются в
следующем разделе). По-английски дерево без выделенного корня называется free
tree. Ориентированный ациклический граф (directed acyclic graph) по-английски
часто сокращают до «dag» (по первым буквам).

Иногда рассматривают обобщения понятия графа. Например, можно рассма-
тривать мультиграф (multigraph), который похож на неориентированный граф,
но может содержать много рёбер, соединяющих одну и ту же пару вершин,
а также рёбра-циклы. Гиперграф (hypergraph) отличается от неориентирован-
ного графа тем, что он содержит гиперрёбра (hyperedges), соединяющие не
две вершины, а произвольное множество вершин. Многие алгоритмы обработки
обычных графов могут быть обобщены на такие графоподобные структуры.

Есть два стандартных способа представить граф G = (V, E) как набор
списков смежных вершин или как матрицу смежности. Первый обычно предпоч-
тительнее, ибо даёт более компактное представление для разреженных (sparse)
графов – тех, у которых | Е| много меньше | V |². Большинство излагаемых нами
алгоритмов используют именно это представление. Однако в некоторых ситуаци-
ях удобнее пользоваться матрицей смежности – например, для плотных (dense)
графов, у которых | Е| сравнимо с | V |². Матрица смежности позволяет быстро
определить, соединены ли две данные вершины ребром.

Представление графа G = (V, Е)в виде списков смежных вершин (adjacency
list representation) использует массив Adj из | V | списков – по одному на вершину.
Для каждой вершины иV список смежных вершин Adj [ u ] содержит в произ
вольном порядке (указатели на) все смежные с ней вершины (все вершины v,
для которых (u, v) Е).

Рисунок 5.3 – Два представления неориентированного графа (списки смежности (б), матрица смежности (в))

Рисунок 5.4 – Два представления ориентированного графа (списки смежности (б), матрица смежности (в))

На рис. 5.3(б) показано представление неориентированного графа
рис. 5.3(а) с помощью списков смежных вершин. Аналогичное представление
для ориентированного графа рис. 5.4(а) изображено на рис. 5.4(б).

Для ориентированного графа сумма длин всех списков смежных вершин
равна общему числу рёбер: ребру (u, v) соответствует элемент v списка Adj [ u ].
Для неориентированного графа эта сумма равна удвоенному числу рёбер, так
как ребро (и, v)порождает элемент в списке смежных вершин как для вер-
шины и, так и для v. В обоих случаях количество требуемой памяти есть
O (max (V, E)) = O (V + Е).

Списки смежных вершин удобны для хранения графов с весами (weight-
ed graphs), в которых каждому ребру приписан некоторый вещественный вес
(weight), то есть задана весовая функция (weight function) . В этом
случае удобно хранить вес w (и, v) ребра (и, v) Е вместе с вершиной v в списке
вершин, смежных с и. Подобным образом можно хранить и другую информацию,
связанную с графом.

Недостаток этого представления таков: если мы хотим узнать, есть ли в
графе ребро из и в v, приходится просматривать весь список Аdj [ u ] в поисках v.
Этого можно избежать, представив граф в виде матрицы смежности, но тогда
потребуется больше памяти.

При использовании матрицы смежности (adjacency matrix) мы нумеруем
вершины графа (V, Е) числами 1,2,..., | V | и рассматриваем матрицу А = ()
размера | V | | V | для которой

На рис. 5.3(в) и 5.4(в) показаны матрицы смежности неориентированного и
ориентированного графов рис. 5.3(а) и 5.4(а) соответственно. Матрица смежно-
сти требует памяти независимо от количества рёбер в графе.

Для неориентированного графа матрица смежности симметрична относи-
тельно главной диагонали (как на рис. 5.3(в)), поскольку (u, v) и (v, u) – это
одно и то же ребро. Другими словами, матрица смежности неориентированного
графа совпадает со своей транспонированной (transpose). (Транспонированием
называется переход от матрицы А = () к матрице , для которой
.)Благодаря симметрии достаточно хранить только числа на главной
диагонали и выше неё, тем самым мы сокращаем требуемую память почти
вдвое.

Как и для списков смежных вершин, хранение весов не составляет проблемы:
вес w (u, v) ребра (u, v) можно хранить в матрице на пересечении и- йстроки и
v -ro столбца. Для отсутствующих рёбер можно записать специальное значение
NIL (в некоторых задачах вместо этого пишут 0 или ).

Для небольших графов, когда места в памяти достаточно, матрица смеж-
ности бывает удобнее – сней часто проще работать. Кроме того, если не надо
хранить веса, то элементы матрицы смежности представляют собой биты, и их
можно размещать по нескольку в одном машинном слове, что даёт заметную
экономию памяти.

При решении многих задач, касающихся графов, необходимы эффективные методы систематического обхода вершин и ребер графов. К таким методам относятся:

- поиск в глубину;

- поиск в ширину.

Эти методы чаще всего рассматриваются на ориентированных графах, но они применимы и для неориентированных, ребра которых считаются двунаправленными.

5.2 Алгоритмы на графах: поиск в ширину, поиск в глубину