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

В неориентированном графе путь (vo, v\,..., Vj~) называется (простым) циклом, если к 3, vq = Vj~ и все вершины t>i, v2, • • •, Vk различны. Например, на рис. 5.2 (б) имеется простой цикл (1, 2, 5,1).

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

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

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

Два графа G = (V, Е) и G = (V, Е) называются изоморфными (isomorphic), если существует взаимно однозначное соответствие /: V -> V между множествами их вершин, при котором рёбрам одного графа соответствуют рёбра другого: (и, v) £ Е тогда и только тогда, когда (f(u),f(v)) £ Е. Можно сказать, что изоморфные графы - это один и тот же граф, в котором вершины названы по-разному. На рис. 5.3 (а) приведён пример двух изо-

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

морфных графов G и G с множествами вершин V = {1, 2, 3,4, 5, 6} и V = {и, v, w, х, у, z}. Функция /: V -> V, для которой /(1) = и, /(2) = v, /(3) = w, /(4) = х, /(5) = у, /(6) = z, является изоморфизмом. Напротив, графы на рис. 5.3 (б) не изоморфны, хотя оба имеют по 5 вершин и по 7 рёбер. Чтобы убедиться, что они не изоморфны, достаточно отметить, что в верхнем графе есть вершина степени 4, а в нижнем - нет.

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

Е = {(u,v) е Е : u,v е V}

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

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

и смежно v. Для неориентированного графа выражения «и - сосед и» и «v смежна с и» являются синонимами.

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

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

Упражнения

5.4-1 На вечеринке каждый гость считает, сколько рукопожатий он сделал. Потом все числа складываются. Покажите, что получится чётное число, доказав следующую лемму о рукопожатиях (handshaking lemma): для неориентированного графа сумма степеней всех его вершин равна удвоенному числу рёбер.

5.4-2 Покажите, что требование к 3 в определении цикла в неориентированном графе существенно (если его отменить, в любом графе, где есть хоть одно ребро, будет цикл).

5.4-3 Докажите, что если в графе (ориентированном или неориентированном) есть путь из вершины и в вершину v, то в нём есть простой путь из и в v. Докажите, что если в ориентированном графе есть цикл, то в нём есть простой цикл.

5.4-4 Покажите, что в связном неориентированном графе (V, Е) число вершин превосходит число рёбер не более чем на 1: \Е\ \V\-l