1. Wat is Boom en Bos?

Boom

• In de grafentheorie wordt a boom is een ongerichte, verbonden en acyclische grafiek . Met andere woorden: een samenhangende graaf die niet eens één cyclus bevat, wordt een boom genoemd.
• Een boom vertegenwoordigt de hiërarchische structuur in grafische vorm.
• De elementen van bomen worden hun knooppunten genoemd en de randen van de boom worden takken genoemd.
• Een boom met n hoekpunten heeft (n-1) randen.
• Bomen bieden veel nuttige toepassingen, zo eenvoudig als een stamboom tot zo complex als bomen in datastructuren van de informatica.
• A blad in een boom bevindt zich een hoekpunt van graad 1, of elk hoekpunt zonder kinderen wordt een blad genoemd.

Voorbeeld

In het bovenstaande voorbeeld zijn het allemaal bomen met minder dan zes hoekpunten.

Woud

In de grafentheorie wordt a woud is een ongerichte, losgekoppelde, acyclische grafiek . Met andere woorden, een onsamenhangende verzameling bomen staat bekend als bos. Elk onderdeel van een bos is een boom.

Voorbeeld

De bovenstaande grafiek lijkt op twee subgrafieken, maar is één enkele, losgekoppelde grafiek. Er zijn geen cycli in de bovenstaande grafiek. Daarom is het een bos.

2. Eigenschappen van bomen

1. Elke boom die minstens twee hoekpunten heeft, moet minstens twee bladeren hebben.
2. Bomen hebben veel karakteriseringen:
   Stel T een grafiek met n hoekpunten, dan zijn de volgende uitspraken equivalent:
   • T is een boom.
   • T bevat geen cycli en heeft n-1 randen.
   • T is verbonden en heeft (n -1) flank.
   • T is een verbonden grafiek en elke rand is een snijkant.
   • Elke twee hoekpunten van grafiek T zijn verbonden door precies één pad.
   • T bevat geen cycli, en voor elke nieuwe rand e heeft de grafiek T+ e precies één cyclus.
3. Elke rand van een boom is afgesneden.
4. Het toevoegen van één rand aan een boom definieert precies één cyclus.
5. Elke verbonden graaf bevat een spanning tree.
6. Elke boom heeft minstens twee hoekpunten van graad twee.

3. Overspannende boom

A overspannende boom in een samenhangende graaf is G een subgraaf H van G die alle hoekpunten van G omvat en tevens een boom is.

Voorbeeld

Beschouw de volgende grafiek G:

Uit de bovenstaande grafiek G kunnen we de volgende drie spanningsbomen H implementeren:

Methoden om de opspannende boom te vinden

We kunnen de spanning tree systematisch vinden met behulp van een van de volgende twee methoden:

1. Afslankmethode
2. Opbouwmethode

1. Afbouwmethode

• Begin met het kiezen van een willekeurige cyclus in grafiek G.
• Verwijder een van de randen van de cyclus.
• Herhaal dit proces totdat er geen cycli meer zijn.

Voorbeeld

• Beschouw een grafiek G,

• Als we de rand ac verwijderen die de cyclus a-d-c-a in de bovenstaande grafiek vernietigt, krijgen we de volgende grafiek:

• Verwijder de rand cb, die de cyclus a-d-c-b-a uit de bovenstaande grafiek vernietigt, dan krijgen we de volgende grafiek:

• Als we de rand ec verwijderen, die de cyclus d-e-c-d uit de bovenstaande grafiek vernietigt, krijgen we de volgende opspannende boom:

2. Opbouwmethode

• Selecteer de randen van grafiek G één voor één. Op zo’n manier dat er geen kringlopen ontstaan.
• Herhaal dit proces totdat alle hoekpunten zijn opgenomen.

Voorbeeld

Beschouw de volgende grafiek G,

converteren van char naar int java

• Kies de rand ab ,

• Kies de rand van ,

• Kies daarna de rand eg ,

• Kies vervolgens de rand cb , dan krijgen we uiteindelijk de volgende opspannende boom:

Circuitrangschikking

Het aantal randen dat we uit G moeten verwijderen om een ​​opspannende boom te krijgen.

Overspannende boom G = m- (n-1) , die de circuit rang van G.

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

Voorbeeld

In de bovenstaande grafiek zijn randen m = 7 en hoekpunten n = 5

Dan is de circuitrang,

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