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

UptoLike

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

Рубрика:

Пример. Графы, изображенные на рис. 1.11 и 1.12 являются компонентами графа на

рис. 1.10.

Рис. 1.11. Рис. 1.12.

● Пусть G = G(V, E) – граф. Циклом называется путь нулевой длины, со-

единяющий вершину саму с собой и не содержащий повторяющихся ребер.

● Простым циклом называется цикл, соединяющий вершину υ саму с со-

бой и не содержащий повторяющихся вершин, кроме υ.

● Цикл называется n – циклом, если он содержит

n ребер и n различных

вершин.

Пример. Если рассмотреть граф на рис. 1.9, то в нем пути υ

являются циклами. При этом все циклы, кроме υ

, простые.

● Граф называется полным, если любые его две вершины соединены реб-

ром.

Полный граф с n вершинами обозначается K

Пример. На рис. 1.13 показаны, соответственно, графы K

, K

Рис. 1.13.

● Граф G = G(V, E) называется двудольным, если V можно представить

как объединение непересекающихся множеств, скажем, V = A

∪

B, так что каж-

дое ребро имеет вид {a, b}, где a

∈

A и b

∈

Таким образом, каждое ребро связывает вершину из A с вершиной из B,

но никакие две вершины из A или две вершины из B не являются связанными.