TechCodeview

1. Шта је дрво и шума?

Дрво

• У теорији графова, а дрво је неусмерени, повезани и ациклични граф . Другим речима, повезани граф који не садржи чак ни један циклус назива се дрво.
• Стабло представља хијерархијску структуру у графичком облику.
• Елементи дрвећа се називају њихови чворови, а ивице дрвета се називају гране.
• Дрво са н врхова има (н-1) ивица.
• Дрвеће пружа многе корисне апликације од једноставних као породично стабло до сложених попут стабала у структурама података рачунарске науке.
• А Лист у дрвету је врх степена 1 или било који врх без деце назива се лист.

Пример

У горњем примеру, сва су стабла са мање од 6 врхова.

Форест

У теорији графова, а шума је неусмерени, неповезани, ациклични граф . Другим речима, неповезана колекција дрвећа позната је као шума. Свака компонента шуме је дрво.

Пример

Горњи график изгледа као два подграфа, али је један неповезани граф. На горњем графикону нема циклуса. Дакле, то је шума.

2. Својства дрвећа

1. Свако дрво које има најмање два врха треба да има најмање два листа.
2. Дрвеће има много карактеристика:
   Нека је Т граф са н врхова, тада су следеће изјаве еквивалентне:
   • Т је дрво.
   • Т не садржи циклусе и има н-1 ивица.
   • Т је повезан и има (н -1) ивицу.
   • Т је повезан граф, а свака ивица је пресечена ивица.
   • Било која два врха графа Т повезана су тачно једном путањом.
   • Т не садржи циклусе, а за било коју нову ивицу е, граф Т+ е има тачно један циклус.
3. Свака ивица дрвета је исечена.
4. Додавање једне ивице стаблу дефинише тачно један циклус.
5. Сваки повезани граф садржи разапињуће стабло.
6. Свако дрво има најмање два врха степена два.

3. Спаннинг Трее

А распонско дрво у повезаном графу Г је подграф Х од Г који укључује све темене Г и такође је дрво.

Пример

Размотрите следећи графикон Г:

Из горњег графикона Г можемо имплементирати сљедећа три размјењива стабла Х:

Методе за проналажење разапињућег дрвета

Можемо да пронађемо разапињуће стабло систематски коришћењем било које од две методе:

1. Метода резања
2. Метода изградње

1. Метода резања

• Почните да бирате било који циклус на графикону Г.
• Уклоните једну од ивица циклуса.
• Понављајте овај процес док не преостане ниједан циклус.

Пример

• Размотримо график Г,

• Ако уклонимо ивицу ац која уништава циклус а-д-ц-а у горњем графикону, добићемо следећи график:

• Уклоните ивицу цб, која уништава циклус а-д-ц-б-а са горњег графика, онда добијамо следећи график:

• Ако уклонимо ивицу ец, која уништава циклус д-е-ц-д са горњег графика, добићемо следеће разапињуће стабло:

2. Метода изградње

• Изаберите ивице графа Г једну по једну. На тај начин да не постоје циклуси се стварају.
• Понављајте овај процес док се сви врхови не укључе.

Пример

Размотримо следећи график Г,

• Изаберите ивицу аб ,

• Изаберите ивицу оф ,

• Након тога, изаберите ивицу ец ,

• Затим изаберите ивицу цб , онда коначно добијамо следеће разапињуће стабло:

Цирцуит Ранк

Број ивица које треба да избришемо из Г да бисмо добили разапињуће стабло.

Разапињуће дрво Г = м-(н-1) , који се зове круг чин од Г.

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

Пример

У горњем графику, ивице м = 7 и темена н = 5

Тада је ранг кола,

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