Fáry-tétel

• IPA:

Fáry-tétel

1. (matematika, gráfelmélet) 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.

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.

---

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

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

---

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

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

---

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 ${\displaystyle n}$-csúcsú síkgráfra létezik egyenes szakaszokkal történő ábrázolás. Mutassuk meg, hogy ez ${\displaystyle n+1}$-csúcsú síkgráfra is igaz.

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

  * Vegyük ${\displaystyle 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 ${\displaystyle 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ő.

---

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.

---

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.

• Fáry-tétel - Értelmező szótár (MEK)
• Fáry-tétel - Etimológiai szótár (UMIL)
• Fáry-tétel - Szótár.net (hu-hu)
• Fáry-tétel - DeepL (hu-de)
• Fáry-tétel - Яндекс (hu-ru)
• Fáry-tétel - Google (hu-en)
• Fáry-tétel - Helyesírási szótár (MTA)
• Fáry-tétel - Wikidata
• Fáry-tétel - Wikipédia (magyar)