Дискретная математика. Громов Ю.Ю - 72 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

72
Следствие 1. Пусть G − связный граф, в котором 2n вершин имеют
нечётные степени, n ≥ 1. Тогда множество рёбер графа G можно раз-
бить на n незамкнутых цепей. ■
Так, неэйлеров граф на рис. 34, а имеет четыре вершины нечётной
степени, а множество его рёбер {a, b, c, d, e, f, g, h} можно разбить на два
подмножества, определяющие незамкнутые цепи (d, a, f, g) и (b, c, h, e).
Следствие 2. Пусть G − связный граф, в котором две вершины
имеют нечётные степени. Тогда в графе G есть незамкнутая цепь, со-
держащая все вершины и все рёбра графа G (и начинающаяся в одной из
вершин с нечётной степенью и кончающаяся в другой). ■
Например, полуэйлеров граф на рис. 34, б имеет две вершины не-
чётной степени и незамкнутую цепь (a, k, m, b, f, e, d, h, g, c), в которой
одна из этих вершин является начальной, а другая − конечной вершиной.
Разделяющим множеством связного графа G называется подмно-
жество его рёбер, удаление которых из графа G приводит к несвязному
графу. Разделяющее множество графа G, никакое подмножество которого
не является разделяющим, называется разрезом графа G. Мостом графа G
называется разрез, состоящий ровно из одного ребра.
Рассмотрим алгоритм построения эйлерова цикла в эйлеровом графе.
Алгоритм Флёри. Пусть G − эйлеров граф. Тогда к эйлерову циклу
графа G приводит следующая процедура. Выходя из произвольной вер-
шины v этого графа, необходимо идти по его рёбрам произвольным об-
разом, соблюдая лишь следующие два правила: 1) стирать рёбра по мере
их прохождения и стирать вершины с нулевой степенью, которые при
этом образуются; 2) на каждом шаге идти по мосту тогда и только
тогда, когда нет других возможностей. ■
Применение алгоритма Флёри к эйлерову графу на рис. 34, в может
дать, например, эйлеров цикл (a, f, g, b, k, m, c, s, p, e, h, d).
Гамильтоновым циклом в связном неориентированном графе G на-
зывается цикл, в котором каждая вершина этого графа содержится ровно
один раз. Граф G называется гамильтоновым графом, если в нём сущест-
вует гамильтонов цикл. Граф G называется полугамильтоновым графом,
если в нём существует простая цепь, содержащая каждую вершину графа
ровно один раз. Граф G, который не является гамильтоновым и не явля-
ется полугамильтоновым графом, будем называть негамильтоновым
графом.
а)
б)
в)
Рис. 37

Страницы