====== 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 [[gráfelmélet#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 [[matematika:logika:teljes indukció]]val.

  - Az egy csúcsú fa éleinek száma nulla.
  - 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:**
  - Ha egy gráfban van két pont, ami közt nincs út, akkor a gráf nem összefüggő - így nem lehet fa.
  - 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 <m 10>{n cdot (n-1)}/2</m>. 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:
<m 10> {n cdot (n-1)}/2 >= 2n doubleright n^2-n>=4n doubleright n^2-5n>=0 </m>
<m 10> n(n-5) >= 0 </m>
Mivel //n// pozitív szám, az egyenlőtlenség megoldása: <m 10>n>=5</m>, 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 ===

  * [[oktatas:matematika:kombinatorika:minimalis_koeltsegu_feszitofa]] keresése

===== Hivatkozások =====
  * [[http://home.fazekas.hu/~lsuranyi/Grafok/bevezeto.htm]]