1. Co je to strom a les?

Strom

• V teorii grafů a strom je neorientovaný, souvislý a acyklický graf . Jinými slovy, souvislý graf, který neobsahuje ani jeden cyklus, se nazývá strom.
• Strom představuje hierarchickou strukturu v grafické podobě.
• Prvky stromů se nazývají jejich uzly a okraje stromu se nazývají větve.
• Strom s n vrcholy má (n-1) hran.
• Stromy poskytují mnoho užitečných aplikací jednoduchých jako rodokmen až po složité jako stromy v datových strukturách informatiky.
• A list ve stromu je vrchol stupně 1 nebo jakýkoli vrchol, který nemá žádné potomky, se nazývá list.

Příklad

Ve výše uvedeném příkladu jsou všechny stromy s méně než 6 vrcholy.

Les

V teorii grafů a les je neorientovaný, odpojený, acyklický graf . Jinými slovy, nesouvislá sbírka stromů je známá jako les. Každá součást lesa je strom.

Příklad

Výše uvedený graf vypadá jako dva podgrafy, ale jedná se o jeden oddělený graf. Ve výše uvedeném grafu nejsou žádné cykly. Proto je to les.

2. Vlastnosti stromů

1. Každý strom, který má alespoň dva vrcholy, by měl mít alespoň dva listy.
2. Stromy mají mnoho charakteristik:
   Nechť T je graf s n vrcholy, pak jsou následující tvrzení ekvivalentní:
   • T je strom.
   • T neobsahuje žádné cykly a má n-1 hran.
   • T je spojen a má (n -1) hranu.
   • T je souvislý graf a každá hrana je řez.
   • Libovolné dva vrcholy grafu T jsou spojeny právě jednou cestou.
   • T neobsahuje žádné cykly a pro každou novou hranu e má graf T+ e právě jeden cyklus.
3. Každá hrana stromu je řezaná.
4. Přidání jedné hrany do stromu definuje přesně jeden cyklus.
5. Každý připojený graf obsahuje kostru.
6. Každý strom má alespoň dva vrcholy stupně dva.

3. Spanning Tree

A kostra v souvislém grafu G je podgraf H grafu G, který zahrnuje všechny vrcholy G a je také stromem.

Příklad

Zvažte následující graf G:

Z výše uvedeného grafu G můžeme implementovat následující tři kostry H:

Metody k nalezení kostry

Spanning tree můžeme systematicky najít pomocí jedné ze dvou metod:

1. Metoda kácení
2. Metoda budování

1. Metoda kácení

• Začněte vybírat libovolný cyklus v grafu G.
• Odstraňte jeden z okrajů cyklu.
• Tento postup opakujte, dokud nezůstanou žádné cykly.

Příklad

• Představte si graf G,

• Pokud odstraníme hranu ac, která zničí cyklus a-d-c-a ve výše uvedeném grafu, dostaneme následující graf:

• Odstraňte hranu cb, která zničí cyklus a-d-c-b-a z výše uvedeného grafu, pak dostaneme následující graf:

• Pokud odstraníme hranu ec, která zničí cyklus d-e-c-d z výše uvedeného grafu, dostaneme následující kostru:

2. Stavební metoda

• Vyberte hrany grafu G jednu po druhé. Tak, aby nevznikaly žádné cykly.
• Tento postup opakujte, dokud nebudou zahrnuty všechny vrcholy.

Příklad

Zvažte následující graf G,

• Vyberte okraj ab ,

• Vyberte okraj z ,

• Poté vyberte okraj ec ,

• Dále vyberte okraj cb , pak nakonec dostaneme následující kostru:

Pořadí obvodu

Počet hran, které potřebujeme odstranit z G, abychom získali kostru.

Kostra G = m- (n-1) , který se nazývá pořadí okruhu z G.

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

Příklad

Ve výše uvedeném grafu jsou hrany m = 7 a vrcholy n = 5

regexp_like v mysql

Pak je pořadí okruhu,

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