Остови графа - це

остов графа

Нехай G - довільний (n, m) -граф з k компонентами зв'язності. Якщо G - не є дерево, то в ньому (його компонентах зв'язності) існують цикли. Розглянемо будь-якої цикл і видалимо з нього якийсь ребро. При цьому кількість компонент зв'язності не збільшиться. Якщо після цього ще залишаться цикли, то розглянемо наступний з них і знову видалимо якесь його ребро. Продовжимо цей процес до тих пір, поки не зникнуть всі цикли. Отриманий в результаті підграф, який, очевидно, є лісом і має стільки ж компонент зв'язності, як і вихідний граф G, називається остовом графа G.

Остов (покриває) деревом графа G називається будь-яке дерево T, що є суграфом графа G. покривають дерево T в зв'язковому графі визначається неоднозначно.

Зв'язний граф має єдине покриває дерево тоді і тільки тоді, коли він сам є деревом.

Остов графа G є мінімальним зв'язковим суграфом графа G, тобто містить мінімальну кількість ребер, що зв'язують вершини графа.

Суграфом T графа G називається каркасом цього графа, якщо він є лісом, який на будь-якому компоненті зв'язності графа G утворює дерево.

Число ребер довільного графа G з n вершинами і m ребрами. має k компонент зв'язності, яке необхідно видалити для отримання остова, не залежить від послідовності їх видалення і так само m-n + k.

доказ теореми

Нехай Hi. i = i, k -компоненти зв'язності графа G, і нехай Hi - (ni, mi) -графи. Після видалення ребер з циклів компоненти Hi вона перетвориться в дерево, яке має ni -1 ребер. Значить, з Hi необхідно видалити mi - (ni -1) ребер. Підсумовуючи за всіма компонентами, знаходимо, що для отримання остова з графа G необхідно видалити (mi -ni +1) = mi - ni + 1 = m-n + k ребер, що й треба було довести.

визначення

Число ν (G) = m-n + k називається цикломатическая числом (циклічним рангом) графа G. Число ν * (G) = n-k, тобто число ребер, що входять в будь-який остов графа G називається його коцікліческім рангом. ν (G) + ν * (G) = m. Кореневим деревом називається дерево T = (V, E) з виділеної вершиною ν, що належить V, при цьому вершина ν називається коренем дерева. Для кожної вершини кореневого дерева її рівень - це довжина ланцюга від кореня до цієї вершини.

Слідство 1 Граф G є лісом тоді і тільки тоді, коли ν (G) = 0.

Слідство 2 Граф G має єдиний цикл тоді і тільки тоді, коли ν (G) = 1.

Слідство 3 Граф G, в якому число ребер не менш, ніж число вершин, має цикл.

Теорема (Кірхгоф)

Число кістяків в зв'язковому графі G порядку n≥2 одно алгебраическому доповнення будь-якого елементу матриці Кирхгофа K ​​(G) графа G.

Теорема. Орграф сильно пов'язаний, якщо в ньому існує остовно циклічний маршрут.

На цю статтю не посилаються інші статті Вікіпедії.

Будь ласка, скористайтеся підказкою та розставте посилання відповідно до прийнятих рекомендацій.