1. Какво е дърво и гора?

Дърво

• В теорията на графите, a дърво е неориентиран, свързан и ацикличен граф . С други думи, свързан граф, който не съдържа нито един цикъл, се нарича дърво.
• Дървото представлява йерархична структура в графична форма.
• Елементите на дърветата се наричат ​​техните възли, а ръбовете на дървото се наричат ​​клони.
• Дърво с n върха има (n-1) ръба.
• Дърветата предоставят много полезни приложения от прости като родословно дърво до толкова сложни като дървета в структурите от данни на компютърните науки.
• А листо в едно дърво е връх от степен 1 ​​или всеки връх, който няма деца, се нарича лист.

Пример

В горния пример всички са дървета с по-малко от 6 върха.

гора

В теорията на графите, a гора е неориентиран, несвързан, ацикличен граф . С други думи, несвързана колекция от дървета е известна като гора. Всеки компонент на гората е дърво.

Пример

Горната графика изглежда като две под-графики, но е една несвързана графика. В горната графика няма цикли. Следователно е гора.

2. Свойства на дърветата

1. Всяко дърво, което има поне два върха, трябва да има поне две листа.
2. Дърветата имат много характеристики:
   Нека T е граф с n върха, тогава следните твърдения са еквивалентни:
   • Т е дърво.
   • T не съдържа цикли и има n-1 ребра.
   • T е свързан и има (n -1) край.
   • T е свързана графа и всяко ребро е срязване.
   • Всеки два върха на графа T са свързани с точно един път.
   • T не съдържа цикли и за всяко ново ребро e, графиката T+ e има точно един цикъл.
3. Всеки ръб на едно дърво е отрязан.
4. Добавянето на едно ребро към дърво дефинира точно един цикъл.
5. Всеки свързан граф съдържа обхващащо дърво.
6. Всяко дърво има поне два върха от степен две.

3. Spanning Tree

А обхващащо дърво в свързан граф G е подграф H на G, който включва всички върхове на G и също е дърво.

Пример

Разгледайте следната графика G:

От горната графика G можем да приложим следните три обхващащи дървета H:

Методи за намиране на обхващащото дърво

Можем да намерим обхващащото дърво систематично, като използваме един от двата метода:

1. Метод на изрязване
2. Метод на изграждане

1. Метод на изсичане

• Започнете да избирате произволен цикъл в графика G.
• Премахнете един от ръбовете на цикъла.
• Повторете този процес, докато не останат никакви цикли.

Пример

• Помислете за графика G,

• Ако премахнем ръба ac, който разрушава цикъла a-d-c-a в горната графика, тогава получаваме следната графика:

• Премахнете ръба cb, който унищожава цикъла a-d-c-b-a от горната графика, тогава получаваме следната графика:

• Ако премахнем ръба ec, който унищожава цикъла d-e-c-d от горната графика, тогава получаваме следното обхващащо дърво:

2. Метод на надграждане

• Изберете ръбовете на графиката G един по един. По такъв начин, че да няма цикли, се създават.
• Повторете този процес, докато не бъдат включени всички върхове.

Пример

Разгледайте следната графика G,

• Изберете ръба аб ,

• Изберете ръба на ,

• След това изберете ръба ек ,

• След това изберете ръба cb , тогава накрая получаваме следното обхващащо дърво:

Ранг на веригата

Броят на ръбовете, които трябва да изтрием от G, за да получим обхващащо дърво.

Обхващащо дърво G = m- (n-1) , което се нарича ранг на веригата на Г.

 Where, m = No. of edges. n = No. of vertices. 

Пример

В горната графика ръбовете m = 7 и върховете n = 5

Тогава рангът на веригата е,

 G = m - (n - 1) = 7 - (5 - 1) = 3