1. Mi az a fa és erdő?

Fa

• A gráfelméletben a fa egy irányítatlan, összefüggő és aciklikus gráf . Más szavakkal, egy olyan összefüggő gráfot, amely egyetlen ciklust sem tartalmaz, fának nevezzük.
• A fa hierarchikus struktúrát ábrázol grafikus formában.
• A fák elemeit csomópontjaiknak, a fa széleit pedig ágaknak nevezzük.
• Egy n csúcsú fának (n-1) éle van.
• A fák számos hasznos alkalmazást kínálnak a számítástechnika adatstruktúráiban, a családfától egészen az olyan összetettig, mint a fák.
• A levél növényen a fában van egy 1. fokú csúcs, vagy bármely olyan csúcsot, amelynek nincs gyermeke, levélnek nevezzük.

Példa

A fenti példában mindegyik fa 6-nál kevesebb csúcsú.

Erdő

A gráfelméletben a erdő van irányítatlan, szétkapcsolt, aciklikus gráf . Más szavakkal, a fák nem összefüggő gyűjteményét erdőnek nevezik. Az erdő minden összetevője fa.

Példa

A fenti gráf két részgráfnak tűnik, de egyetlen szétválasztott gráf. A fenti grafikonon nincsenek ciklusok. Ezért ez egy erdő.

2. A fák tulajdonságai

1. Minden fának, amelynek legalább két csúcsa van, legalább két levelűnek kell lennie.
2. A fáknak számos jellemzőjük van:
   Legyen T egy n csúcsú gráf, akkor a következő állítások ekvivalensek:
   • T egy fa.
   • T nem tartalmaz ciklusokat, és n-1 éle van.
   • T összefüggő és (n -1) éle van.
   • T egy összefüggő gráf, és minden él egy vágóél.
   • A T gráf bármely két csúcsát pontosan egy út köti össze.
   • T nem tartalmaz ciklusokat, és minden új e él esetén a T+ e gráfnak pontosan egy ciklusa van.
3. A fa minden éle vágott él.
4. Egy él hozzáadása egy fához pontosan egy ciklust határoz meg.
5. Minden összefüggő gráf tartalmaz egy feszítőfát.
6. Minden fának van legalább két második fokú csúcsa.

3. Átfogó fa

A feszítőfának egy összefüggő gráfban G a G egy H részgráfja, amely tartalmazza G összes csúcsát, és egyben fa is.

megjegyzések tavaszi csizmában

Példa

Tekintsük a következő G grafikont:

A fenti G grafikonból a következő három H feszítőfát tudjuk megvalósítani:

Módszerek az átívelő fa megtalálására

A feszítőfát szisztematikusan megtalálhatjuk két módszer valamelyikével:

pawandeep rajan

1. Vágási módszer
2. Felépítési módszer

1. Kivágási módszer

• Kezdje el bármelyik ciklus kiválasztását a G grafikonon.
• Távolítsa el a ciklus egyik szélét.
• Ismételje meg ezt a folyamatot, amíg már nem marad ciklus.

Példa

• Tekintsünk egy G gráfot,

• Ha a fenti gráfban eltávolítjuk az a-d-c-a ciklust tönkretevő ac élt, akkor a következő gráfot kapjuk:

• Távolítsuk el a cb élt, amely tönkreteszi az a-d-c-b-a ciklust a fenti gráfból, és a következő gráfot kapjuk:

• Ha eltávolítjuk a d-e-c-d ciklust tönkretevő ec éleket a fenti gráfból, akkor a következő feszítőfát kapjuk:

2. Felépítési módszer

• Jelölje ki egyenként a G gráf éleit. Oly módon, hogy nincsenek ciklusok jönnek létre.
• Ismételje meg ezt a folyamatot, amíg az összes csúcsot bele nem foglalja.

Példa

Tekintsük a következő G grafikont,

• Válassza ki a szélét ab ,

• Válassza ki a szélét nak,-nek ,

• Ezután válassza ki a szélét ec ,

• Ezután válassza ki a szélét cb , akkor végül a következő feszítőfát kapjuk:

Circuit Rank

Az élek száma, amelyeket törölnünk kell G-ből, hogy feszítőfát kapjunk.

Feszítőfa G = m- (n-1) , amelyet a áramköri rang G.

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

Példa

A fenti gráfban az élek m = 7 és a csúcsok az n = 5

ms word gyorselérési eszköztár

Ekkor az áramkör rangja:

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