Fáry-tétel

1. Sablon:Label A Fáry-tétel vagy Fáry–Wagner-tétel kimondja, hogy bármely egyszerű síkbarajzolható gráf beágyazható a síkba úgy is, hogy a gráf éleit egyenes szakaszok alkotják.

---

Fáry-tétel

A **Fáry-tétel** a gráfelmélet egy fontos eredménye, amely az egyszerű síkgráfok egy speciális rajzát biztosítja. A tétel kimondja, hogy minden síkgráf ábrázolható úgy a síkon, hogy az élek egyenes szakaszok legyenek.

---

Tétel

Legyen $G=(V,E)$ egy síkgráf, azaz $G$ rajzolható úgy a síkra, hogy élei nem metszik egymást. Ekkor $G$ ábrázolható a síkon olyan módon, hogy:

• minden él egyenes szakasz legyen,
• az élek továbbra sem metszik egymást.

---

Bizonyítás

1. Előfeltételek

• $G$ egy síkgráf, tehát létezik olyan rajz, amelyben $G$-nek nincs élmetszése.
• Az Euler-formula biztosítja, hogy a síkgráfok topológiai struktúrája megfelelően kezelhető:

$$|V|-|E|+|F|=2,$$ ahol $F$ a síkgráf síkbeli régióinak száma.

---

2. Indukció a csúcsszámra

Bázis: Egy háromszög (triviális síkgráf) nyilvánvalóan ábrázolható úgy, hogy minden éle egyenes szakasz legyen.

Indukciós lépés: Tegyük fel, hogy minden $n$-csúcsú síkgráfra létezik egyenes szakaszokkal történő ábrázolás. Mutassuk meg, hogy ez $n+1$-csúcsú síkgráfra is igaz.

1. Kétoldalú fa (triangulált gráf):

  * Vegyük $G$-t, és trianguláljuk (azaz adjunk hozzá éleket, ha szükséges, hogy minden régió háromszög legyen). A triangulált gráf is síkgráf marad.

2. Középpontos ábrázolás (barycentrikus koordináták):

  * Válasszuk ki $G$ egy tetszőleges külső háromszögét, amelyet rögzítsünk a koordináta-rendszerben.
  * A fennmaradó csúcsokat helyezzük el a háromszög súlypontja szerint oly módon, hogy minden belső csúcs a szomszédos csúcsok középpontja legyen (barycentrikus elhelyezés).

3. Indukció zárása:

  * Mivel minden csúcs pontosan egy régióhoz tartozik, a triangulált gráf ábrázolása egyenes szakaszokkal is elvégezhető.

---

Következmények

1. Planáris gráfok egyenes ábrázolása:

Minden planáris gráf síkban ábrázolható úgy, hogy az élek egyenesek.

1. Gráfok geometriája:

A Fáry-tétel az alapja a síkgráfok geometriájának és vizualizációjának, mivel garantálja, hogy az egyenes szakaszokkal való ábrázolás lehetséges.

1. Számítógépes gráfrajzok:

Algoritmusokat lehet kidolgozni arra, hogy planáris gráfokat egyenes szakaszokkal ábrázoljunk, például a barycentrikus koordináták használatával.

---

Összefoglalás

A **Fáry-tétel** kimondja, hogy minden síkgráf ábrázolható a síkon úgy, hogy az élek egyenes szakaszok legyenek, és ne metszék egymást. Ez a tétel alapvető a gráfelmélet vizualizációs problémáiban és a planáris gráfok geometriai megértésében.

• Sablon:En: Sablon:T