9. előadás tételei

Fák ekvivalens jellemzése Tétel

Ha \(G\) egyszerű gráf, akkor a következő állítások ekvivalensek:

1. \(G\) fa
2. \(G\) körmentes, de ha bárhová behúzunk egy élt, kör keletkezik.
3. \(G\) bármelyik 2 csúcsa között pontosan 1 út van.
4. \(G\) összefüggő, de bármelyik élt elhagyva már nem az.

Fák ekvivalens jellemzése Bizonyítás

1. \(\Rightarrow\) 2 Körmentes

   Behúzunk \(G\)-be +1 élt, \(v_1\) és \(v_2\) közé. De \(G\) összefüggő, tehát volt út \(v_1\) és \(v_2\) között, ezért a behúzott éllel kör keletkezett.

2. \(\Rightarrow\) 3 \(v_1\) és \(v_2\) között út létezik

   Ha behúznék egy élt, keletkezne új kör, ebben szerepel az új él. A kör többi éle egy út \(v_1\) és \(v_2\) között.

   Csak 1 út van:

   Ha lenne 2 út, akkor azok között lenne egy kör, de \(G\) körmentes.

3. \(\Rightarrow\) 4 \(G\) összefüggő, de bármelyik élt elhagyva már nem az

   Ha elhagyható lenne egy él, akkor nem lenne körmentes, hisz az elhagyott él után már nem lehet út \(v_1\) és \(v_2\) között.

4. \(\Rightarrow\) 1 \(G\) fa

   • Összefüggő \(\checkmark\)
   • Körmentes \(\checkmark\) (1. biz miatt)

Tétel

Ha \(G\) egy véges körmentes véges gráf legalább 1 éllel \(\Rightarrow\) \(\exists\) benne elsőfokú csúcs.

Bizonyítás

Keressük meg a leghosszabb (egyik) utat \(G\)-ben. Ennek a végpontjai elsőfokúak, mert ha nem lennének azok, akkor ez nem lehetne a leghosszabb út.

Tétel

\(n \in \mathbb{N}^+\). Egy \(n\) csúcsú \(G\) egyszerű gráfra ekvivalensek a következő állítások:

1. \(G\) fa
2. \(G\)-nek (n-1) éle van, és körmentes
3. \(G\)-nek (n-1) éle van, és összefüggő

Bizonyítás

1. \(\Rightarrow\) 2 \(G\)-nek \(n-1\) éle van és körmentes

   Indukció:

   n=1 \(\rightarrow\) 0 él

   n-re tudjuk \(\Rightarrow\) (n+1)-re?

   n+1 csúcsú fa \(\Rightarrow\) \(\exists\) elsőfokú csúcs: \(v\)

   Ha az elsőfokú csúcsot, és a hozzá tartozó élt elhagyjuk, akkor egy \(n\) csúcsú fa keletkezik \(\Rightarrow\) (n-1) él \(\Rightarrow\) \(G\): n él n = (n+1)-1

2. \(\Rightarrow\) 3 (n-1) éle van, és összefüggő

   Indukció n=1 \(\checkmark\)

   n-re tudjuk \(\Rightarrow\) (n+1)-re?

   LEMMA: \(\exists\) elsőfokú csúcs

   Ind. feltevés \(\Rightarrow\) eltávolítva az elsőfokú csúcsot (az élek?) \(\Rightarrow\) összefüggő a kapott gráf \(\Rightarrow\) \(G\) is összefüggő

3. \(\Rightarrow\) 1 \(G\) fa

   KELL: Körmentes a gráf

   Ha nem lenne az, akkor ismételten, hagyjunk el körökből éleket, amíg végül körmentes lesz \(\Rightarrow\) FA

Tétel

\(G\)-nek \(\exists\) feszítőfája \(\Longleftrightarrow\) \(G\) összefüggő

Bizonyítás (véges \(G\)-re)

Ha \(G\) összefüggő \(\Rightarrow\) addig hagyjuk el belőle a körben szereplő éleket, amíg körmentes nem lesz. Ekkor \(G\)-nek van feszítőfája.

Tétel

Egy \(n\) csúcsú, \(e\) élű összefüggő gráfba \(\exists e-n+1\) db kör, melyek páronként különböző élhalmazúak.

Bizonyítás

Tekintsük \(G\) egy feszítőfáját: \((n-1)\) él.

A feszítőfán kívül van \(e-(n-1)=e-n+1\) db él.

Ezen extra élek közül bármelyiket hozzávéve a feszítőfához, kör keletkezik. \(\rightsquigarrow\) ha mindig csak az ilyen élt veszünk hozzá, akkor páronként kölönbözőek a körök.