5.1.1 Графы

Ориентированный граф (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).

В неориентированном графе путь называется (простым) цик- лом, если k3, и все вершины различны. Например, на рис. 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), соединяющие не две вершины, а произвольное множество вершин. Многие алгоритмы обработки обычных графов могут быть обобщены на такие графоподобные структуры.