Часть I. Теория графов

1. Основные понятия

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

1.1. Основные определения

Граф G = (V, Е) состоит из двух множеств: конечного множества элементов, называемых вершинами, и конечного множества элементов, называемых ребрами. Каждое ребро определяется парой вершин. Если ребра графа определяются упорядоченными парами вершин, то G называется направленным или ориентированным графом. В противном случае G называется ненаправленным или неориентированным графом. В первых четырех главах книги рассматриваются ненаправленные графы.

Для обозначения вершин графа будем использовать символы а для обозначения ребер — . Вершины и определяющие ребро называются концевыми вершинами ребра . В этом случае ребро обозначается как . Заметим, что в множестве Е допускается более чем одно ребро с одинаковыми концевыми вершинами. Все ребра с одинаковыми концевыми вершинами называются параллельными. Кроме того, концевые вершины ребра не обязательно различны. Если то ребро называется петлей. Граф называется простым, если он не содержит петель и параллельных ребер. Граф G является графом порядка , если множество его вершин состоит из элементов.

Граф, не имеющий ребер, называется пустым. Граф, не имеющий вершин (и, следовательно, ребер), называется нуль-графом.

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

ребра, петля. Говорят, что ребро инцидентно своим концевым вершинам. Две вершины смежны, если они являются концевыми вершинами некоторого ребра. Если два ребра имеют общую концевую вершину, они называются смежными.

Например, в графе на рис. 1.1 ребро инцидентно вершинам являются смежными вершинами, а — смежными ребрами.

Число инцидентных вершине - ребер называется степенью вершины и обозначается Иногда степень вершины называется также ее валентностью. Вершина степени 1 называется висячей вершиной. Единственное ребро, инцидентное висячей вершине, называется висячим. Вершина степени 0 называется изолированной. По определению петля при вершине добавляет 2 в степень соответствующей вершины. Величины обозначают минимальную и максимальную степени вершины в G соответственно.

Рис. 1.1. Граф .

В графе G на рис.

Заметим, что — изолированная вершина, — висячие ершины, — висячее ребро. Легко проверить, что сумма степеней ершин в данном графе G равна 10, тогда как число ребер равно 5. аким образом, сумма степеней вершин графа G равна удвоенному ислу ребер графа G и, следовательно, является четным числом. того, можно показать, что число вершин графа G нечетной тепени также четно. Эти результаты свойственны не только графу а рис. 1.1. Они справедливы, как доказывается в следующих теоремах, для всех графов.

Теорема 1.1. Сумма степеней вершин графа G равна где — число ребер графа G.

Доказательство. Поскольку каждое ребро инцидентно двум вершинам, оно обавляет двойку к сумме степеней графа G. Следовательно, все ребра дают вместе умму степеней

Теорема 1.2. Число вершин нечетной степени в любом графе четно. Доказательство. Пусть число вершин в графе G равно . Не нарушая общности, предположим, что степени первых вершин четны, а степени ставшихся вершин нечетны. Тогда

По теореме 1.1 сумма в левой части выражения (1.1) четна. Первая сумма правой части также четна, поскольку каждый член суммы четный. Следовательно,

вторая сумма в правой части должна быть четной. Так как каждый член этой суммы нечетный, то число членов в сумме должно быть четным. Другими словами, число вершин нечетной степени должно быть четным.