11.6. лес. разрезы

11.6. лес. разрезы

Граф, не содержащий циклов и состоящий из к компонент, называется к-деревом; Аг-дерево графа G, содержащее все его вершины, называется остовным.

Подграф G, содержащий все его вершины и только те ребра, которые не входят в остовное к-дерево Т графа G, называется к-кодеревом Т*.

Если граф G содержит к компонент, то его остовное ^-дерево Т называется лесом, а Ажодерево Т* в этом случае называется

ко-лєсом.

На рис. 11.7 изображены остовное 2-дерево Тж 2-кодерево Т* графа G, представленного на рис. 11.6. На рис. 11.8 изображены граф G, содержащий две компоненты, его лес Г и ко-лес Т*.

Рангом графа G, имеющего и вершин и состоящего из к компонент, называется число

r(G) = n-k (11.2)

312

i(G) = m-n + k, (11.3)

где т — число ребер графа G;n — число вершин; к — число компонент.

Ранг и цикломатическое число связаны соотношением

r(G) + i(G) = m. (11.4)

Теорема. Ранг r(G) графа G равен числу ребер леса, а цикломатическое число u(G) равно числу ребер ко-леса.

Ранг и цикломатическое число являются числовыми характеристиками графа, определяющими размерность подпространств циклов и разрезов.

313

Пусть есть некоторый связный граф G, множество вершин которого разбито на два непустых непересекающихся подмножества: Р = Рх и Рт Тогда множество всех ребер G, имеющих одну концевую вершину в Pv а другую — в Р2, называется разрезом графа G.

11.7. Эйлеровы и гамильтоновы графы

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

На рис. 11.9 граф G не является эйлеровым, так как вершинар3 инцидентна только одному ребру. Если путь приведет в вершину ру то не будет ребра, по которому можно было бы выйти из ру

Теорема. Граф Gявляется эйлеровым тогда и только тогда, когда G связный и все его вершины имеют четную степень.

Граф G, изображенный нарис. 11.10, является эйлеровым. Последовательность ребер (ар ос2, ос3, ос4, ос5, ос6, а7, а8, а9, а10) образует эйлеров цикл.

Теорема. Граф G обладает эйлеровым путем с концами рх, р2 тогда и только тогда, когда G связный и рх, р2 — единственные его вершины нечетной степени.

На рис. 11.9 изображен граф G, обладающий эйлеровым путем (оСр ос2, ос3, а4, а5, а6) с концевыми вершинамир5 иру

Гамильтоновым путем (циклом) графа называется путь (цикл), проходящий через каждую вершину графа в точности по одному разу. Граф, обладающий гамильтоновым циклом, называется гамильтоновым графом.

Критерий существования гамильтонова цикла в произвольном графе G еще не найден. Достаточным условием существования гамильтонова цикла является полнота графа G.

Граф на рис. 11.9 не является гамильтоновым, а граф на рис. 11.11 содержит гамильтонов цикл (av ос2, а4, ос5, а6).