Графы и сети. Харитонова Е.В. - 15 стр.

UptoLike

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

Рубрика:

Ориентированный граф является связным, поскольку его соотнесенный

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

скольку из υ

в υ

не существует ориентированного пути.

1.3 Пути и циклы Эйлера

● Пусть G = G(V, E) – граф. Цикл, который включает все ребра и верши-

ны графа G, называется эйлеровым циклом.

Если это условие выполняется, говорят, что граф G имеет эйлеров цикл.

ТЕОРЕМА 1.4. Граф с более чем одной вершиной имеет эйлеров

цикл

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

степень.

Пример. Граф на рис. 1.26 имеет эйлеров цикл, поскольку степень каждой его верши-

ны четная, граф на рис. 1.27 не имеет эйлерова цикла, поскольку степени вершины υ

и υ

–

нечетные.

Рис. 1.26 Рис. 1.27

● Пусть G = G(V, E) – граф. Путь, который включает каждое ребро графа

G только один раз называется эйлеровым путем.

В этом случае говорят, что граф G имеет эйлеров путь.

● Если эйлеров путь не является эйлеровым циклом, то такой путь назы-

вают собственным эйлеровым путем.

ТЕОРЕМА 1.5. Граф (мультиграф

или псевдограф) имеет собственный

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

имеют нечетную степень.

Пример. Граф на рис. 1.28 имеет собственный эйлеров путь, т.к. ровно две его вер-

шины имеют нечетную степень. Граф на рис. 1.29 не имеет собственного эйлерова пути, т.к.

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

d υ