5.1. Определения

Предметом первых задач в теории графов были конфигурации, состоящие из точек и соединяющих их линий. В этих рассмотрениях было несущественно, прямые ли это линии или же они являются криволинейными непрерывными дугами, соединяющими две концевые точки, где расположены эти линии, являются ли они длинными или короткими. Существенно только то, что они соединяют две данные точки.

Это приводит к определению графа как абстрактного математического понятия. Рассматривается множество V, состоящее из соединенных некоторым образом точек. Назовем V множеством вершин и элементы v из V — вершинами. Граф

G = (V, E) (5.1)

с множеством вершин V есть некоторое семейство сочетаний или пар вида

Е = (а,b), где a, b из V, (5.2)

указывающее, какие вершины считаются соединенными.

В соответствии с геометрическим представлением графа каждая конкретная пара (5.2) называется ребром графа; вершины а и b называются концевыми точками или концами ребра Е.

Можно использовать и другой подход. Если даны два множества V₁ и V₂, то можно образовать множество всех пар (v₁,v₂), где v₁ из V₁, v₂ из V₂. Это множество пар называется (прямым) произведением и обозначается через V₁×V₂. В нашем случае каждая пара вершин (а,b) есть элемент произведения V×V. Таким образом, можно сказать, что граф G из (5.1) с заданными ребрами (5.2) есть некоторое подмножество произведения V×V.

Это определение графа должно быть дополнено в одном важном отношении. В определении ребра (5.2) можно принимать или не принимать во внимание порядок расположения двух его концов. Если этот порядок не существенен, т. е. если E = (а,b) = (b,а), то говорят, что Е есть неориентированное ребро; если же этот порядок существен, то Е называется ориентированным ребром.

Граф G, не содержащий ориентированных рёбер, называется неориентированным. В дальнейшем будем рассматривать только неориентированные графы.

Говорят, что ребро Е из (5.2) инцидентно вершинам а и b, a также что а и b инцидентны Е.

В приложениях граф G обычно интерпретируется как сеть, в которой вершинами G являются узлы. Два узла a и b соединяются непрерывной кривой (в частности, прямолинейным отрезком) тогда и только тогда, когда в графе G есть пара (5.2). На рисунках узлы будут обычно обозначаться маленькими кружками, а рёбра - дугами.

Вершина, не инцидентная никакому ребру, называется изолированной.

Граф, состоящий только из изолированных вершин, называется нуль - графом и обозначается через 0. Другим важным случаем является (неориентированный) полный граф, ребрами которого являются всевозможные пары (5.2) для двух различных вершин а и b из V. На рис. 5.1 даны схемы полных графов для множеств вершин из четырех и пяти элементов. Сформулированное выше определение графа, вместе с соответствующим изображением, достаточно для многих задач. Однако для некоторых целей желательно понятие графа несколько расширить. Во-первых, можно допускать ребра, у которых концевые вершины совпадают:

L = (a,a) (5.3)

Такое ребро называется петлей. При изображении графа петля бу-

дет представляться замкнутой дугой, возвращающейся в вершину a и не проходящей через другие вершины (рис. 5.2). Во-вторых, можно расширить понятие графа, допуская, чтобы пара вершин соединялась несколькими различными ребрами, у которых обе концевые точки совпадают, как это изображено на рис. 5.3. Такие рёбра назы-

Рис. 5.1. Полные графы для множеств вершин из четырёх и пяти элементов

Рис. 5.2. Петля

Рис. 5.3. Параллельные рёбра

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

В дальнейшем мы будем рассматривать только графы с конечным числом вершин и рёбер.