§1. Определения

Дадим сначала определение простого графа G. Пара (V(G), Е(G)) называется простым графом, если V(G) -- непустое конечное множество элементов, называемых вершинами (или узлами, или точками), а Е(G) -- конечное множество неупорядоченных пар различных элементов из V(G), называемых ребрами (или линиями). Иногда V(G) называют множеством вершин, а Е(G) -- множеством ребер графа G. Например, на Рис. 1 изображен простой граф G, у которого множеством вершин V(G) является множество {u, v, w, z}, а множество ребер Е(G) состоит из пар {u, v}, {v, w}, {u, w} и {w, z}. Говорят, что ребро {v, w} соединяет вершины v и w. Отметим, что так как Е(G) является множеством, а не семейством, то в простом графе данную пару вершин может соединять не более чем одно ребро.

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

Рис. 1. Рис. 2

Получающийся при этом объект, в котором могут быть петли и кратные ребра, называется общим графом, или просто графом (Рис. 2). Подчеркнем тот факт, что каждый простой граф является графом, но не каждый граф является простым графом.

Более точно, графом G называется пара (V(G), Е(G)), где V(G) -- непустое конечное множество элементов, называемых вершинами, а Е(G) -- конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых ребрами. Заметим, что употребление слова «семейство» говорит о том, что допускаются кратные ребра. Будем называть V(G) множеством вершин, а Е(G) -- семейством ребер графа G; на Рис. 2 V(G) -- это множество {u, v, w, z}, а Е(G) -- это семейство, состоящее из ребер {u, v}, {v, v), {v, v), {v, w}, {v, w}, (v, w}, {u, w}, {u, w} и {w, z}. О каждом ребре вида {v, w} говорят, что оно соединяет вершины v и w; значит, каждая петля {v, v} соединяет вершину v саму с собой. Предметом изучения в теории графов являются также ориентированные графы (называемые иногда орграфами или сетями; однако мы будем употреблять слово «сеть» в несколько ином смысле). Орграфом D называется пара (V(D), A (D)), где V(D) -- непустое конечное множество элементов, называемых вершинами, а А (D) -- конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами). Дуга, у которой вершина v является первым элементом, а вершина w -- вторым, называется дугой из v в w и обозначается (v, w). Заметим, что дуги (v, w) и (w, v) различны. На Рис. 3 изображен орграф, дугами которого являются (u, v), (v, v), (v, w), (v, w), (w, v), (w, u) и (w, z); порядок вершин на дуге указан стрелкой.

Рис 3

Рис. 4

Графы и орграфы -- существенно различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги (Рис. 4).

Замечание по поводу терминологии. Язык теории графов, бесспорно, еще не стал стандартным -- каждый автор вводит свою собственную терминологию. Я пользуюсь в основном терминологией Басакера и Саати . Некоторые специалисты по теории графов называют графом то, что мы назвали простым графом. Во многих случаях, и особенно в приложениях, под графом понимается орграф. Еще хуже, иногда графом называют объект, который получается, если снять условие конечности множества вершин или семейства ребер. (Если оба они бесконечны, будем называть соответствующий объект бесконечным графом; изучение бесконечных графов мы отложим до §8.) Следует подчеркнуть, что любое из перечисленных определений графа вполне допустимо, если только пользоваться им последовательно.

Прежде чем привести примеры некоторых важных типов графов (§3), удобно дать еще несколько простых определений.

Две вершины v и w графа G называются смежными, если существует соединяющее их ребро (т. е. ребро вида {v, w}); при этом вершины v и w называются инцидентными этому ребру (а ребро -- инцидентным этим вершинам). Аналогично, два различных ребра графа G называются смежными, если они имеют по крайней мере одну общую вершину. Степенью (или валентностью) вершины v графа G называется число ребер, инцидентных v; степень вершины v обозначается через с(v). При вычислении степени вершины v будем учитывать петлю в v два раза, а не один (если только явно не сказано иное). Вершина степени 0 называется изолированной вершиной, вершина степени 1 называется висячей (или концевой) вершиной. Так, граф, изображенный на Рис. 2, имеет одну висячую вершину, одну вершину степени 3, одну -- степени 6 и одну -- степени 8.

Легко видеть, что если сложить степени всех вершин графа, то получится четное число -- равное удвоенному числу ребер, так как каждое ребро участвует в этой сумме ровно два раза. Этот результат, известный еще двести лет назад Эйлеру, часто называют леммой о рукопожатиях. Из нее следует, что если несколько человек обменялись рукопожатиями, то общее число пожатых рук обязательно четно, ибо в каждом рукопожатии участвуют две руки (при этом каждая рука считается столько раз, сколько она участвовала в рукопожатиях). Из леммы о рукопожатиях сразу следует, что в любом графе число вершин нечетной степени должно быть четным.

Рис. 5

Два графа G₁ и G₂ называются изоморфными, если существует взаимно однозначное соответствие между множествами их вершин, обладающее тем свойством, что число ребер, соединяющих любые две вершины в G₁, равно числу ребер, соединяющих соответствующие вершины в G₂. Так, два графа, изображенные на Рис. 5, изоморфны при соответствии u-l, v-m, w-n, x-p, y-q. Заметим, что эти графы имеют по шесть вершин -- другие точки пересечения ребер вершинами не являются.

Подграфом графа G называется граф, все вершины которого принадлежат V(G), а все ребра принадлежат Е(G). Так, граф на Рис. 1 является подграфом графа, изображенного на Рис. 4, но не является подграфом ни одного из графов, приведенных на Рис. 5 (так как последние не содержат «треугольников»).

Наконец, матрицей смежности графа G с множеством вершин {v₁, ..., v_n} (соответствующей данной нумерации вершин) называется матрица А = (а_ij) размера n xn, в которой элемент а_ij равен числу ребер в G, соединяющих v_i и v_j. Например, на Рис. 6 дана матрица смежности графа, изображенного на Рис. 4. Можно получить несколько различных матриц смежности данного графа, меняя обозначения его вершин; это приведет к изменению порядка строк и столбцов матрицы A. Но в результате всегда получится симметричная матрица из неотрицательных целых чисел, обладающая тем свойством, что сумма чисел в любой строке или столбце равна степени соответствующей вершины (здесь каждая петля учитывается в степени вершины один раз).

Рис. 6

Обратно, по любой заданной симметричной матрице из неотрицательных целых чисел легко построить граф (единственный с точностью до изоморфизма), имеющий данную матрицу своей матрицей смежности. Отсюда следует, что теорию графов можно свести к изучению матриц особого типа.