9. Fák és jellemzésük

Question 1

Erdők, fák

Answer 1

• Körmentes gráfokat erdőnek, míg körmentes összefüggő gráfokat fáknak nevezzük.
• Egy erdő komponensei fák, azaz egy erdő nem más mint fák diszjunkt uniója.
• Fák és erdők mindig egyszerű gráfok.
• Egy gráf akkor és csak akkor fa, ha bármely két csúcsa között pontosan egy út van.
• Fa ⇔ minimális összefüggő gráf.

Question 2

Erdők, fák - következtetések

Answer 2

• Ha minden pont foka legalább 2, akkor a gráfban van kör. Észrevétel: Ha van kör a G-ben, összefüggő ⇒ a körnek bármely élét elhagyva a gráfból ⇒ G még mindig összefüggő. Észrevétel: Bármely összefüggő gráfból élek elhagyhatók ⇒ G fa.
• Ha egy tetszőleges (egyszerű) gráfban nincs kör, akkor van legalább 2 első fokú pontja.
• Ha egy $G=(V,E)$ gráfban nincs kör, akkor $|E| ≤ |V | -1$ .
• Ha egy $G=(V,E)$ gráf összefüggő, akkor $|E| ≥ |V | -1$ .
• Ha $G=(V,E)$ tetszőleges összefüggő gráf és $|E| = |V | -1$, akkor $G$ körmentes, azaz fa.

Question 3

Összefoglaló tétel:

Answer 3

Tetszőleges $G$ gráf esetén az alábbi 3 tulajdonság közül egyik sem vonja maga után semelyik másikat, de bármely kettőből következik a harmadik, vagyis:
1.) $G$ összefüggő
2.) $G$ körmentes
3.) $|E| = |V | -1$

Question 4

Cayle tétele:

Answer 4

• Tetszőleges $n∈ \N$ természetes számra $n^{n−2}$ páronként nem izomorf, számozott csúcsú fa gráf van n csúcson.
• A tétel kimondja, hogy bármely $( n )$ természetes számra létezik $( n^{n-2} )$ különböző számozott fa, ahol a fák csúcsai $( n )$ számozott csúcsból állnak.

Question 5

Prüfer kód(tétel):

Answer 5

• Fa csúcsainak számozását felhasználva minden fát, kölcsönösen egy-egy értelmű módon, egy-egy $(n-2)$ hosszúságú számsorozattal, ú.n. “Prüfer-kóddal” azonosít, vagyis kódol, amelyből egyértelműen lehet rekonstruálni a fát.

Question 6

Feszítő fa:

Answer 6

• Tetszőleges $G=(V,E)$ gráf $T=(W,F) \subseteq G$ részgráfját feszítőfának nevezzük, ha $W=V$, azaz T tartalmazza G minden csúcsát, és T fa (körmentes és összefüggő).