Tartalomjegyzék

Fa

Fa: A körmentes, összefüggő, egyszerű gráfokat fának nevezzük.

Állítás: Egy fa mindig tartalmaz elsőfokú pontot.

Bizonyítás: Nulla fokú, azaz izolált pont nem lehet a fában, mert a fa összefüggő.
Ha az összes pont legalább másodfokú lenne, akkor a gráfban lenne kör (korábbi tétel szerint) - így nem lehetne fa.

Állítás: Egy fa mindig legalább két elsőfokú csúcsot tartalmaz.

Bizonyítás: A fának van elsőfokú csúcsa. Induljunk el belőle élek mentén haladva. Így egy utat járunk be, hisz pont nem ismétlődhet - mivel a fa körmentes. Az egymáshoz csatlakozó élek előbb-utóbb elfogynak. Az utolsó csúcs szükségképpen elsőfokú.

Állítás: Az n csúcsú fa éleinek száma n-1.

Bizonyítás: A pontok száma szerinti teljes indukcióval.

  1. Az egy csúcsú fa éleinek száma nulla.
  2. Tegyük fel, hogy a k csúcsú fa éleinek számáról tudjuk, hogy k-1.

Vegyünk most egy k+1 csúcsú fát. Ebben a fában biztosan van elsőfokú csúcs (különben lenne benne kör - egy másik tétel miatt) Hagyjuk el ezt a pontot a rá illeszkedő éllel együtt. Ekkor egy k pontból álló, továbbra is összefüggő, körmentes gráfot, azaz fát kapunk. Mivel ennek k-1 éle kell legyen az indukciós feltevés miatt, így a k+1 csúcsú fának eggyel több, azaz k éle volt.

Állítás: Egy gráf pontosan akkor fa, ha bármely két csúcsa között pontosan egy út van.

Bizonyítás:

  1. Ha egy gráfban van két pont, ami közt nincs út, akkor a gráf nem összefüggő - így nem lehet fa.
  2. Ha a gráfban van két pont melyek közt van (legalább) két különböző út, akkor a gráfban van kör, így a gráf nem lehet fa. Keressük meg ugyanis a két út első „elágazását” (legyen ez P csúcs), azaz az első olyan csúcsot, amely után a két útban különböző él következik. Ilyen pont bizotsan van, mert a kezdőpont közös, de az összes él nem lehet azonos. Keressük meg az első úton az e P csúcsot követő csúcsok közül az első közös csúcsot - legyen ez Q. Ilyen is biztos van - legrosszabb esetben a végpont. Az így kiválasztott P és Q között az első úton csupa olyan él van, amit a második út nem tartalmaz, így ezekhez fűzve a második út Q és P közé eső szakaszát kört kapunk.

Állítás: Egy fából kiindulva tetszőleges él hozzáadásával egy kör keletkezik.

Bizonyítás: Kösse össze az új él P és Q csúcsokat. Ekkor P és Q között a fában pontosan egy út vezet. Ehhez hozzávéve az új élt kört kapunk.

Következmény: Ha egy n csúcsú összefüggő gráfnak n éle van, akkor a gráfban van kör. A gráf feszítőfájából egy él hozzáadásával jutunk a gráfhoz.

Állítás: Ha egy G gráf legalább 5 csúcsú, akkor G vagy G komplementere közül legalább az egyik tartalmaz kört.

Bizonyítás: Az n pontú teljes gráf éleinek száma {n cdot (n-1)}/2. Ha ez a szám legalább 2n, akkor a G és G komplementer közül legalább az egyik minimum n élt tartalmaz. Lássuk mikor teljesül ez a feltétel: {n cdot (n-1)}/2 >= 2n doubleright n^2-n>=4n doubleright n^2-5n>=0 n(n-5) >= 0 Mivel n pozitív szám, az egyenlőtlenség megoldása: n>=5, ami épp az állítás feltétele volt.

Legyen például G legalább n élt tartalmazó gráf. Ha nem összefüggő, akkor van benne olyan komponens, melyben az élek száma nem kevesebb a csúcsok számánál, ugyanis ha az összes komponens kevesebb élt tartalmazna, mint ahány csúcsot, akkor az élek száma a teljes gráfban is kevesebb lenne, mint a csúcsok száma.

Legyen tehát a K komponens olyan, melyben az élek száma nem kevesebb a pontok számánál: ekkor K tartalmaz kört (az előző állítás következménye miatt).

Feszítőfa

Állítás: Minden összefüggő gráfból kiválasztható olyan összefüggő körmentes részgráf, mely a gráf összes pontját tartalmazza. Az ilyen részgráfot a gráf feszítőfájának nevezzük.

Bizonyítás: Ha a gráfban nincs kör, akkor a gráf maga a feszítőfa. Ha van benne kör, akkor a körböl hagyunk el egy tetszőleges élt. Ekkor a gráf továbbra is összefüggő marad, de a körök száma (legalább eggyel) csökken. Véges számú lépésben élek elhagyásával az összes kör megszűntethető.

Nevezetes feladatok

Hivatkozások