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

UptoLike

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

Рубрика:

Рис. 1.28 Рис. 1.29

● Пусть G = G(V, E) – ориентированный граф.

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

длины из вершины в ту же вершину без повторения ребер.

● Пусть G = G(V, E) – ориентированный граф.

Ориентированный цикл, которого включает все ребра и вершины графа

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

ТЕОРЕМА 1.6. Ориентированный граф имеет

эйлеров цикл тогда и толь-

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

выхода.

Пример. Ориентированный граф на рис. 1.30 имеет эйлеров цикл, так как степень

входа каждой вершины равна степени выхода. Ориентированный граф на рис. 1.31 не имеет

эйлерова цикла, так как степень входа вершины υ

не равна ее степени выхода.

Рис. 1.30 Рис. 1.31

1.4 Планарные графы

Интегральная микросхема состоит из слоев миниатюрных микросхем,

впечатанных в пластину. В такой ситуации важно исключить пересечение про-

водов в местах, не предназначенных для соединений. Если изобразить места

указанных соединений вершинами графа, то возникает задача построения графа

с непересекающимися ребрами. Важно отметить, что интересует возможность

построения графа с непересекающимися

ребрами.

c b

●d