1. Mikä on puu ja metsä?

Puu

• Graafiteoriassa a puu on suuntaamaton, yhdistetty ja asyklinen graafi . Toisin sanoen yhdistettyä kuvaajaa, joka ei sisällä edes yhtä sykliä, kutsutaan puuksi.
• Puu edustaa hierarkkista rakennetta graafisessa muodossa.
• Puiden elementtejä kutsutaan solmuiksi ja puun reunoja oksiksi.
• Puulla, jossa on n kärkeä, on (n-1) reunaa.
• Puut tarjoavat monia hyödyllisiä sovelluksia niin yksinkertaisista kuin sukupuusta niin monimutkaisiin kuin puut tietojenkäsittelytieteen tietorakenteissa.
• A puun lehti puussa on asteen 1 kärki tai mitä tahansa kärkeä, jolla ei ole lapsia, kutsutaan lehdeksi.

Esimerkki

Yllä olevassa esimerkissä kaikki ovat puita, joissa on vähemmän kuin 6 kärkeä.

Metsä

Graafiteoriassa a metsä On suuntaamaton, irrotettu, asyklinen graafi . Toisin sanoen hajanainen puiden kokoelma tunnetaan metsänä. Jokainen metsän osa on puu.

Esimerkki

Yllä oleva kaavio näyttää kahdelta alikaaviolta, mutta se on yksi irrotettu graafi. Yllä olevassa kaaviossa ei ole jaksoja. Siksi se on metsä.

2. Puiden ominaisuudet

1. Jokaisessa puussa, jossa on vähintään kaksi kärkeä, tulee olla vähintään kaksi lehteä.
2. Puilla on monia ominaisuuksia:
   Olkoon T graafi, jossa on n kärkeä, niin seuraavat lauseet ovat ekvivalentteja:
   • T on puu.
   • T ei sisällä jaksoja ja siinä on n-1 reunaa.
   • T on kytketty ja sillä on (n -1) reuna.
   • T on yhdistetty graafi, ja jokainen reuna on leikkausreuna.
   • Mikä tahansa kaksi graafin T kärkeä on yhdistetty täsmälleen yhdellä polulla.
   • T ei sisällä jaksoja, ja mille tahansa uudelle reunalle e graafissa T+ e on täsmälleen yksi jakso.
3. Puun jokainen reuna on leikattu.
4. Yhden reunan lisääminen puuhun määrittää tarkalleen yhden syklin.
5. Jokainen yhdistetty graafi sisältää virittävän puun.
6. Jokaisella puulla on vähintään kaksi toisen asteen kärkeä.

3. Virtaava puu

A ylittävä puu yhdistetyssä graafissa G on G:n aligraafi H, joka sisältää kaikki G:n kärjet ja on myös puu.

Esimerkki

Harkitse seuraavaa kuvaajaa G:

Yllä olevasta kaaviosta G voimme toteuttaa seuraavat kolme virittävää puuta H:

Menetelmät ylittävän puun löytämiseksi

Voimme löytää virittävän puun systemaattisesti käyttämällä jompaakumpaa kahdesta menetelmästä:

1. Leikkausmenetelmä
2. Rakennusmenetelmä

1. Leikkausmenetelmä

• Aloita minkä tahansa syklin valitseminen kaaviosta G.
• Poista yksi syklin reunoista.
• Toista tämä prosessi, kunnes jaksoja ei ole jäljellä.

Esimerkki

• Tarkastellaan kuvaajaa G,

• Jos poistamme reunan ac, joka tuhoaa syklin a-d-c-a yllä olevassa kaaviossa, saamme seuraavan graafin:

• Poista reuna cb, joka tuhoaa syklin a-d-c-b-a yllä olevasta graafista, jolloin saadaan seuraava graafi:

• Jos poistamme reunan ec, jotka tuhoavat syklin d-e-c-d yllä olevasta graafista, saadaan seuraava virittävä puu:

2. Rakennusmenetelmä

• Valitse graafin G reunat yksi kerrallaan. Sillä tavalla, että syklejä ei synny.
• Toista tämä prosessi, kunnes kaikki kärjet ovat mukana.

Esimerkki

Tarkastellaan seuraavaa kuvaajaa G,

• Valitse reuna ab ,

• Valitse reuna / ,

• Valitse sen jälkeen reuna ec ,

• Valitse seuraavaksi reuna cb , niin lopulta saamme seuraavan virittävän puun:

Piirin sijoitus

Niiden reunojen määrä, jotka meidän on poistettava G:stä, jotta saadaan virittävä puu.

Virtaava puu G = m- (n-1) , jota kutsutaan nimellä piirin sijoitus G.

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

Esimerkki

Yllä olevassa kaaviossa reunat m = 7 ja kärjet n = 5

Sitten piirin arvo on,

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