04. Эйлеров цикл и эйлеров граф. Условия существования эйлерова цикла. Задача о разбиении графа на минимальное число цепей

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

Обойти по всем ребрам, пройдя каждое ребро только один раз. Граф, обладающий эйлеровым циклом, сам называется Эйлеровым.

Вот пример эйлерова графа:

А вот пример графа, не являющегося эйлеровым:

Существует теорема (Теорема Эйлера), полностью описывающая эйлеровы графы:

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

Таким образом, имеется конкретный способ устанавливать, является или нет данный граф эйлеровым. Однако, если граф окажется эйлеровым, то указать его эйлеров цикл можно только после дополнительных исследований.

В связи с эйлеровыми графами имеется одна классическая задача О минимальном цепном разбиении. Вот ее формулировка.

Пусть - Связный граф и - все его вершины Нечетной степени (на-помним, что в каждом графе число вершин нечетной степени четно). Тогда, если , То минимальное число цепей графа, содержащих в совокупности все его ребра, равно ; Если же , То указанное минимальное число равно 1.

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

построим новый граф , в котором (т. е. добавляется одна новая вершина) и (т. е. добавляется еще ребер);

заметим, что полученный граф является связным и все его локальные степе-ни уже четны; поэтому в нем существует некий эйлеров цикл ;

осуществим обход по циклу , начав и закончив этот обход в вершине ; те цепей, о которых идет речь в обсуждаемом утверждении, будут выделяться в процессе этого обхода так: обход начинается в вершине ; следовательно, следующей за будет некая вершина из G; она и будет началом первой цепи; после некоторого пути надо будет вновь вернуться в ; первая цепь закончится в той вершине из G, из которой осуществится возвращение в ; затем по той

< Предыдущая		Следующая >