Составители:
Рубрика:
92
всегда возможно на каждом шаге. (Если v = u, то
доказательство не меняется, если имеются ребра,
инцидентные u). Покажем, что данная процедура
приводит к эйлерову пути. Действительно, в G не
может быть ребер, оставшихся не пройденными по-
сле использования последнего ребра, инцидентного
u, поскольку в противном случае удаление ребра,
смежного одному
из оставшихся, привело бы к не-
связному графу, что противоречит условию 2).
3.4. Некоторые родственные задачи
Сразу же укажем ряд вопросов, связанных с
тем, имеется ли в неориентированном графе эйле-
ров цикл. Например:
1) Каково наименьшее число цепей или циклов не-
обходимое для того, чтобы каждое ребро графа
G содержалось точно в одной цепи или в одном
цикле? Очевидно, что если G имеет эйлеров
цикл или эйлерову цепь, то ответом будет число
один.
2) Ребрам графа G приписаны положительные ве-
са. Требуется найти цикл, проходящий через
каждое ребро графа G по крайней мере один раз
и такой, что для него общий вес (а именно сум-
ма величин n
j
.c.(a
j
), где число n
j
показывает,
сколько раз проходилось ребро a
j
, а c.(a
j
) – вес
ребра) минимален. Очевидно, что если G содер-
жит эйлеров цикл, то любой такой цикл будет
85
Теорема 2.13. Для любого неорграфа G без петель
выполняется неравенство
J
(G) } deg (G) + 1.
0B3. Эйлеровы циклы
3.1. Основные понятия и определения
Дадим строгое определение эйлерову циклу
и эйлерову графу.
Определение 3.1. Если граф имеет цикл (не обяза-
тельно простой), содержащий все ребра графа по
одному разу, то такой цикл называется эйлеровым
циклом, а граф называется эйлеровым графом.
Определение 3.2. Если граф имеет цепь (не обяза-
тельно простую), содержащую все вершины по
одному разу, то такая цепь называется эйлеровой
цепью, а граф называется полуэйлеровым графом.
Ясно, что эйлеров цикл содержит не только
все ребра по одному разу, но и все вершины графа
(возможно, по несколько раз). Очевидно также,
что эйлеровым
может быть только связный граф.
Выберем в качестве вершин графа берега ре-
ки, а в качестве ребер – мосты, их соединяющие.
После этого задача становится очевидной: требо-
вание неосуществимо – чтобы его выполнить, чис-
ло дуг, приходящих к каждой вершине, должно
быть четным. В самом деле, поскольку по одному
мосту нельзя проходить
дважды, каждому входу
на берег должен соответствовать выход.
всегда возможно на каждом шаге. (Если v = u, то Теорема 2.13. Для любого неорграфа G без петель
доказательство не меняется, если имеются ребра, выполняется неравенство J (G) } deg (G) + 1.
инцидентные u). Покажем, что данная процедура
приводит к эйлерову пути. Действительно, в G не 3. Эйлеровы циклы
0B
может быть ребер, оставшихся не пройденными по- 3.1. Основные понятия и определения
сле использования последнего ребра, инцидентного Дадим строгое определение эйлерову циклу
u, поскольку в противном случае удаление ребра, и эйлерову графу.
смежного одному из оставшихся, привело бы к не- Определение 3.1. Если граф имеет цикл (не обяза-
связному графу, что противоречит условию 2). тельно простой), содержащий все ребра графа по
3.4. Некоторые родственные задачи одному разу, то такой цикл называется эйлеровым
Сразу же укажем ряд вопросов, связанных с циклом, а граф называется эйлеровым графом.
тем, имеется ли в неориентированном графе эйле- Определение 3.2. Если граф имеет цепь (не обяза-
ров цикл. Например: тельно простую), содержащую все вершины по
одному разу, то такая цепь называется эйлеровой
1) Каково наименьшее число цепей или циклов не- цепью, а граф называется полуэйлеровым графом.
обходимое для того, чтобы каждое ребро графа Ясно, что эйлеров цикл содержит не только
G содержалось точно в одной цепи или в одном все ребра по одному разу, но и все вершины графа
цикле? Очевидно, что если G имеет эйлеров (возможно, по несколько раз). Очевидно также,
цикл или эйлерову цепь, то ответом будет число что эйлеровым может быть только связный граф.
один. Выберем в качестве вершин графа берега ре-
2) Ребрам графа G приписаны положительные ве- ки, а в качестве ребер – мосты, их соединяющие.
са. Требуется найти цикл, проходящий через После этого задача становится очевидной: требо-
каждое ребро графа G по крайней мере один раз вание неосуществимо – чтобы его выполнить, чис-
и такой, что для него общий вес (а именно сум- ло дуг, приходящих к каждой вершине, должно
ма величин nj.c.(aj), где число nj показывает, быть четным. В самом деле, поскольку по одному
сколько раз проходилось ребро aj, а c.(aj) – вес мосту нельзя проходить дважды, каждому входу
ребра) минимален. Очевидно, что если G содер- на берег должен соответствовать выход.
жит эйлеров цикл, то любой такой цикл будет
92 85
