Маршруты, циклы в неориентированном графе

Пусть G – неориентированный граф. Маршрутом в графе G называется такая последовательность (конечная или бесконечная) ребер a₁, a₂, ... a_n..., что каждые два соседних ребра a_i и a_i+1 имеют общую инцидентную вершину. Одно и то же ребро может встречаться в маршруте несколько раз. В конечном маршруте (a₁, a₂, ... a_n) имеется первое ребро a₁ и последнее ребро a_n. Вершина x₁, инцидентная ребру a₁, но не инцидентная ребру a₂, называется началом маршрута, а вершина x_n, инцидентная ребру a_n, но не инцидентная ребру a_n-1, называется концом маршрута.

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

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

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

На рис. 13 изображены два маршрута из вершины x₁ в вершину x₄: M₁ = (a₁, a₂, a₄) и M₂ = (a₁, a₂, a₅, a₆). Длина маршрута M₁ равна 3, а длина маршрута M₂ равна 4.

Рисунок 13

	(a1,a3,a4) – простая элементарная цепь длины 3, так как все ребра и вершины попарно различны.
	(a2,a4,a3) – простой элементарный цикл, так как это замкнутый маршрут, у которого все ребра и верши­ны, кроме первой и последней, различны.
	(a1,a2,a4,a3) – цепь, которая является простой, но не элементарной, так как все ребра различны, но вершина x2 встречается дважды.
	(a1,a2,a2) – маршрут длины 3, не являющийся ни простой, ни элементарной цепью, т.к. ребро a2 и вершина x2 встречаются дважды.

Пути, контуры в ориентированном графе

Понятия пути и контура в ориентированном графе аналогичны понятиям маршрута и цикла в неориентированном графе.

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

Число дуг пути называется длиной пути.

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

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

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

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

Неориентированный граф	Ориентированный граф
ребро маршрут цикл	дуга путь контур

Пример.

Рисунок 14.

В приведенном на рис. 14 графе выделим следующие пути:

• (x₁,x₂,x₃,x₄) – простой элементарный путь, т.к. каждая вершина и каждая дуга используются не более одного раза;

• (x₂,x₅,x₆,x₇,x₂) – простой элементарный контур, т.к. это замкнутый путь, в котором все дуги и вершины, кроме первой и последней, различны.

Гамильтонова цепь (путь, цикл, контур) − простая цепь (путь, цикл, контур), проходящая через все вершины.

Эйлерова цепь (путь, цикл, контур) − цепь (путь, цикл, контур), содержащая все ребра (дуги) графа по одному разу.

Число ребер графа можно определять различными способами. Наиболее простой способ – прямой пересчет ребер. Другой способ использует понятие степеней вершин графа.

Пример.

Рассмотрим граф типа a (см. рис. 16) и подсчитаем степени его вершин. Получим: (А)=2, (B)=3, (C)=3, (D)=2, (E)=3, (F)=3.. Если просуммировать степени всех вершин и разделить это число пополам, получим количество ребер графа. Так, для графа типа a имеем .

В общем случае, пусть вершины графа обозначены A_i (i = 1,n), тогда число ребер графа определяется по формуле (1)

Формула (1) для определения числа ребер графа применима как для графов с кратными ребрами, так и для графов с петлями. Следует только правильно подсчитывать степени вершин. Для этого нужно вокруг вершины провести маленькую окружность так, чтобы в нее не попала полностью петля. После чего подсчитать количество ребер, проходящих в этой окружности к вершине. Так, для вершины B графа с (см. рис. 16) получаем (B)=5, а для вершины D того же графа ( D)=6.

Число ребер этого графа , что соответствует значению, полученному прямым пересчетом.

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

Во всех примерах графов это действительно так. Если бы был найден граф, у которого количество вершин нечетной степени было бы нечетным, то из формулы (1) следовало бы, что число ребер этого графа было бы нецелым.

Возможная интерпретация этой теоремы: на любом мероприятии (банкете, приеме и т.д.) число лиц, совершивших нечетное число рукопожатий, четно или таких лиц нет вовсе.