Математическое моделирование на графах. Часть 1. Берцун В.Н. - 54 стр.

UptoLike

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

Рубрика:

54 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1

Рис. 2.10

Эйлеровой цепью (в цепи ребро не встречается дважды) в графе

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

называется цикл, содержащий все ребра графа в точности один раз.

Граф, обладающий эйлеровым циклом, называется эйлеровым гра-

фом.

Утверждение 2.3. Если граф G обладает эйлеровым циклом, то

он связный и все его вершины имеют четную степень.

Доказательство. Связность графа следует из определения эйле-

рова цикла. В эйлеровом цикле каждое ребро встречается только

один раз, а каждая вершина встречается k ≥ 1 раз (или k + 1 раз, если

это начальная и конечная вершины цикла, которые совпадают). По-

этому все вершины графа должны иметь четную степень 2k. ■

Утверждение 2.4. В графе G из всякого цикла можно выделить

простой цикл.

Доказательство. Если длина цикла L = 1, то цикл есть петля и он

прост. Пусть утверждение верно для всех графов с циклами длины

до L – 1. Рассмотрим цикл длины L. Он либо простой, либо в нем

есть вершины, повторяющиеся более одного раза. Цикл, сущест-

вующий на таких вершинах, имеет длину меньше L и поэтому со-

держит простой цикл. ■

Утверждение 2.5. Если граф G связный и все его вершины имеют

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

Доказательство. Для петли, состоящей из одного ребра, эйлеров

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

m – 1 есть эйлеров цикл. У графа G с m ребрами четные степени

вершин, поэтому он имеет хотя бы один простой цикл С. Если этот

цикл содержит все ребра графа G, то С – эйлеров цикл. Если С не

эйлеров цикл, то удалив из G все ребра цикла С, получим суграф G

В таком суграфе каждая компонента связности является либо изоли-