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

Граф состоит из множества вершин X и множества ребер U. Вершины обычно обозначают кружками, ребра - прямыми линиями, а сам граф - буквой G.

Если у графа n вершин и m ребер, то он обозначается

G(X,U), X = {x₁, x₂, ... , x_n } = {x_i }, i = 1, n;

U = {u₁, u₂, ... , u_m } = {u_j }, j = 1,m.

Рис. 4.1. Парк в городе

Кенигсберге, 1736 г.

x₁

x₂x₃

x₄

Рис. 4.2. Граф к задаче

о кенигсбергских мостах

x₁u₁x₂

u₅u₄u₂

x₄u₃x₃

Рис.4.3. Определение графа

Для графа, изображенного на рис.4.3:

X = {x₁, x₂, x₃, x_4} = {x_i}, i = 1,4;

U = {u₁, u₂, u₃, u₄, u₅} = {u_j}, j = 1,5 = {(x₁, x₂), (x₂, x₃), (x₃, x₄), (x₄, x₂), (x₁, x₄)}.

Следует отметить, что в определении графа не указывается, как он изображен на плоскости, а дается лишь совокупность связей между вершинами. Поэтому изображенные на рис.4.4 графы G₁,G₂ и G₃представляют один и тот же граф.

x₁

x₁x₂G₂ x₁x₂

G₁ G₃

x₂

Рис.4.4. Изображение графа на плоскости

Ребро графа соединяет всегда две вершины, которые называются смежными. Так для ребра u₃ (рис.4.3) смежными являются вершины x₃и x₄. Ребро же u₃ является инцидентным как вершине x₃, так и вершине x₄.

Степенью вершины x_i (deg x_i) графа G называется число ребер, инцидентных x_i, i = 1, n.

Для графа на рис.4.3 deg x₁ = 2, deg x₂ = 3.

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

deg x_i = 2 × m

Доказательство теоремы основано на инцидентности каждого ребра двум вершинам графа.

Два графа называются изоморфными, если они равны с точностью до переобозначения вершин и ребер.

y₁y₂

y₄ y₃

Рис.4.5. Изоморфизм графов

Граф G из примера 4.3 и граф H (рис.4.5) изоморфны, что следует из переобозначения вершин:

y₁x₂, y₂x₃, y₃x₄, y₄x₁.

Граф с кратными ребрами называется мультиграфом (рис.4.6). Если же допускаются петли, то получаем псевдограф (рис.4.7).

Рис.4.6. Мультиграф Рис.4.7. Псевдограф

Граф H называется подграфом графа G, если все его вершины и ребра принадлежат G, H Ì G (рис.4.8).

x₂

x₄x₃

Рис.4.8. Подграф

Граф H является подграфом графа G, изображенного на рис.4.3.

Граф G называется полным, если каждая пара его вершин смежная. Полный граф из n вершин обозначается K_n. На рис.4.9 изображены полные графы для

n = 1, 2, 3, 4, 5.

K₃ K₄ K₅

K₁K₂

Рис.4.9. Полные графы

Граф G называется двудольным, если множество его вершин X можно разбить на два подмножества X1 и X2, X = X1 È X2, X1 Ç X2 = Æ таким образом, что каждое ребро графа G соединяет вершины из разных множеств (рис.4.10). Один из изображенных на этом рисунке графов – K_3,3 называется полным трех вершинным двудольным графом.

G G = K_{3, 3}

Рис.4.10. Двудольные графы

Граф G называется планарным, если его можно изобразить на плоскости без пересечений ребер.

Граф K₄ (рис.4.9) является планарным. Одна из его плоских укладок изображена на рис.4.11.

K₄

Рис.4.11. Плоская укладка графа K₄

Графы K₅ и K_{3, 3} являются не планарными, то есть их нельзя уложить на плоскости без пересечений ребер. Не планарность графа K_{3, 3} лежит в основе известной задачи М.Гарднера.

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

Оказывается, что это невозможно. На рис.4.12 показана одна из таких попыток.

Рис.4.12. Укладка на плоскости графа K_{3, 3}

Удивительные свойства плоских графов видны на примере следующей задачи.

Пусть на плоскости дано изображение плоского графа G. Перенумеруем его вершины и снова изобразим их на плоскости произвольным образом. Спрашивается, можно ли соединить новое расположение вершин ребрами таким образом, чтобы граф G оставался плоским?

Оказывается это возможно. Плоский граф инвариантен относительно размещения на плоскости его вершин (рис.4.13).

y y

1 3 5

3 2

6 1 4

6 5 4

0 x 0 x

Рис. 4.13. Инвариантность плоского графа относительно

расположения на плоскости его вершин

Маршрутом в графе G называется чередующаяся последовательность смежных вершин и ребер.

Маршрут называется цепью, если все его ребра различны.

Маршрут называется простой цепью, если все его вершины (а, следовательно, и ребра) различны.

Если в цепи начальная вершина совпадает с конечной, то она называется циклом.

Если в простой цепи начальная вершина совпадает с конечной, то она называется простым циклом.

x₁x₂ x₃

x₅ x₄

Рис.4.14. Граф G

Для графа G на рис. 4.14:

x₁ x₂x₃x₂x₅ - маршрут

x₂ x₅x₃x₂x₁ - цепь

x₂x₅x₃x₄ - простая цепь

x₂x₅x₃x₄x₅x₁ x₂ - цикл

x₂x₅ x₄x₃x₂ - простой цикл

Граф называется ориентированным (орграфом), если каждому его ребру приписано направление (рис.4.15).

Любая пара смежных вершин называется дугой. Пусть дуга связывает x с y (рис.4.15).

Полу степенью исхода od(x) называется число вершин, смежных из x.

Полу степенью захода id(y) называется число вершин, смежных к y.

На рис.4.15 od(x₅) = 1, id(x₂) = 2.

x₅x₁x₂

G x y

x₄ x₃

Рис.4.15. Ориентированный граф

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

Маршрут, в котором все вершины различны, называется путем.

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

Для графа G на рис.4.15:

x₁x₂x₃x₄x₂x₃x₄x₅ - ориентированный маршрут

x₁x₂x₃x₄x₅ - путь

x₄x₂x₃x₄ - контур

Длина маршрута (цепи, простой цепи, цикла, простого цикла, ориентированного маршрута, пути, контура) d равна числу входящих в него ребер (дуг).

Для графа G на рис.4.14:

d(x₁x₂x₃x₄x₅) = 4

Для графа G на рис.4.15:

d(x₄x₂x₃x₄) = 3

Расширим понятие графа. Поставим в соответствие каждому ребру графа G неотрицательное число w_j> 0, j = 1, m.