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).
Обсуждение Справочник по математике для экономистов
Комментарии, рецензии и отзывы