Пути и контуры в графах

Существует понятие цепей в теории графов. Связка вершин и ребер образует цепь в графе. Цепь называется полной, если она связывает все вершины графа без образования петель и контуров. Цепь имеет голову и хвост. Голова цепи привязывается к какой-либо вершине, которую называют привязкой. Цепи образуют пути в графе.

Путь в неориентированном графе G – это последовательность ребер и вершин L (v_0, х₁, v₁, х₂, v₂, х₃, v₃, x _n, v _n), где v – вершины, x – ребра. При этом вершина v₀ называется началом пути, вершина v _n – концом. Каждая прочая вершина инцидентна предыдущему ребру и последующему, поскольку конец каждого ребра совпадает с началом следующего.

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

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

Теорема 4.1. Неориентированный граф является эйлеровым тогда и только тогда, когда он связен и все степени его вершин четны.

Необходимость. То, что в несвязном графе не может быть цикла, проходящего через все ребра, очевидно. Пусть теперь граф связен и в нем существует эйлеров цикл с началом в вершине v₁. Пройдем по этому циклу, помечая пройденные ребра. Через каждую вершину цикл может проходить несколько раз, добавляя каждый раз два помеченных ребра. При каждом проходе через вершину v₁ будет помечено нечетное число ребер (потому что при первом выходе из v₁ было помечено одно ребро), а при проходах через другие вершины – четное число ребер. Поэтому цикл может закончиться в v₁ только в том случае, когда степень v₁ четна (цикл входит по последнему непомеченному ребру, и к нечетному числу помеченных ребер добавляется единица). Во всех остальных вершинах все ребра будут помеченными, т. е. число помеченных ребер в каждой вершине будет равно ее степени, которая тем самым окажется четной.

Пути и связность в ориентированных графах. Путь в ориентированном графе G_О – это последовательность вершин v₀, v₁,… v_n, такая, что v_i → v_i+1 для любого i, если i+1 существует.

Ряд понятий для неориентированных графов – начало, конец, длина пути, цикл, цепь, простая цепь – без изменения переносятся на орграфы. Другие понятия, и прежде всего связность и достижимость, существенно видоизменяются. Говорят, что вершина v_j достижима из вершины v_i , если суще­ствует путь с началом в v_i и концом в v_j. По определению полагаем, что любая вершина достижима из себя самой.

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

Отношение достижимости между вершинами в оргра­фах несимметрично: если v_j достижима из v_i, то v_i необязательно достижима из v_j.

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

Таким образом, в орграфах существуют различные виды связности, которые описываются следующими определениями.

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

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

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

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

Длиной пути называется число ребер от вершины v_i к вершине v_j. Длина может быть различной для пути между двумя вершинами.

Если рассматривать путь с минимальным числом ребер от вершины v_i к вершине v_j, то такой путь называется расстоянием r (v_i; v_j). Если между вершинами не существует никакого пути, то r = ∞.

Диаметром d(G) графа G называется максимальное расстояние между его вершинами:

d(G) = max d(v_i; v_j).

Для любой вершины можно определить среднее отклонение от центра графа по формуле

D (v_i) = 1/m∑ r(v_i; v),

где m – число дуг в графе G, а v – пробегает все вершины графа.

Вершина, для которой D(v_i) окажется минимальной, называется центром графа. Может быть несколько вершин, являющихся центром.

Максимальное удаление r (v_i) от центра графа называется радиусом графа G и обозначается r (G).

Рассмотрим орграф G₁ с количеством вершин n = 6 и числом дуг m = 12, изображенный на рис. 4.13.

Построим матрицу R=|| r_ij ||, которая отражает все расстояния между вершинами графа G₁. На ее основе можно рассчитать все возможные отклонения вершин от центра графа:

D₁ = 8/12; D₂ = 8/12; D₃ = 9/12; D₄ = 13/12; D₅ = 11/12; D₆ = 7/12.

Таким образом, вершина v₆ является центром графа G₁.

2 1 2 3 4 5 6

1 0 2 1 2 2 1 1

3 2 0 1 2 2 1 2

2 1 0 3 1 2 3

R(G₁) = 2 4 3 0 1 3 4

6 1 3 2 3 0 2 5

1 1 2 1 2 0 6

Рис. 4.13

Матрица смежности А(G₁) дает число путей, длина которых равна одной дуге. Квадрат матрицы А²(G₁) дает число путей, длина которых равна двум. Куб матрицы А³(G₁) – число путей в три дуги и т.д.

Дата добавления: 2014-01-07