síkgráf-elválasztási tétel

Magyar

Kiejtés

• IPA: [ ˈʃiːɡraːfɛlvaːlɒstaːʃiteːtɛl]

Főnév

síkgráf-elválasztási tétel

1. (matematika, gráfelmélet) A síkgráf-elválasztási tétel egy fontos eredmény a gráfelméletben, amely azt mondja ki, hogy bármely síkgráf csúcsai bizonyos feltételek mellett kettéválaszthatók két részre úgy, hogy az elválasztás egy kicsi élhalmaz segítségével történik.

A tétel kimondja:

Egy síkgráf $G$ $n$ csúccsal kettéválasztható két részre úgy, hogy az egyes részekben lévő csúcsok száma legfeljebb ${\frac {2n}{3}}$, és az elválasztó csúcsok száma legfeljebb $2{\sqrt {2\cdot n}}$.

Ez a tétel különösen hasznos a gráfelméletben és a számítástechnikában, például gráfalgoritmusok hatékonyságának javításában.

Fogalmak

Síkgráf

- Egy gráf síkgráf, ha rajzolható síkba úgy, hogy élei nem metszik egymást.

Gráf elválasztása

- Egy gráf elválasztása egy olyan felosztás, ahol a gráf csúcsai két részre oszlanak úgy, hogy a köztük lévő élek számát minimalizáljuk.

Elválasztási tétel alapelve

- Egy síkgráf „gyengén összefüggő”, azaz a gráf egyensúlyos felosztása kis számú él vagy csúcs eltávolításával elérhető.

Bizonyítás

1. Síkgráf tulajdonságai

A síkgráfok Euler-féle tulajdonságára építünk: $v-e+f=2,$ ahol:

• $v$: csúcsok száma,
• $e$: élek száma,
• $f$: régiók (területek) száma.

Egy síkgráf esetén: $e\leq 3v-6.$

2. Felosztási algoritmus

1. Átmérő:

  - Válasszunk ki egy tetszőleges $v_{0}$ csúcsot.
  - Számítsuk ki az ${\text{d}}(v_{0},v)$ távolságot minden más $v$ csúcstól (a legrövidebb utak hossza szerint).

1. Közelítő „középső” kör:

  - Tekintsük a gráf azon $v$ csúcsait, amelyek távolsága $r$-nél kisebb vagy egyenlő.
  - Ha $r$ megfelelően választott (a gráf méretéhez igazítva), a körhöz tartozó csúcsok száma korlátozott lesz.

1. Elválasztó halmaz:

  - A kör mentén kiválasztott csúcsok az elválasztó halmazt alkotják.
  - Ezeket eltávolítva a gráf két részre esik szét, amelyek csúcshalmazai $S_{1}$ és $S_{2}$.

3. Felosztás tulajdonságai

- Az $S_{1}$ és $S_{2}$ részekben lévő csúcsok száma legfeljebb ${\frac {2n}{3}}$. - Az elválasztó csúcsok száma legfeljebb $2{\sqrt {2n}}$, mivel a síkgráf geometriai tulajdonságai ezt garantálják.

4. Következtetés

Az elválasztási eljárás mindig elvégezhető úgy, hogy az elválasztó halmaz (csúcsok vagy élek) mérete korlátozott legyen.

Példa

Gráf

Legyen egy síkgráf $G$ 18 csúccsal és 27 éllel.

1. Csúcsok és élek tulajdonságai:

$e=27,\quad v=18,\quad f=e-v+2=11.$

1. Elválasztási eljárás:

  - A gráf átmérője alapján válasszunk egy körhalmazt az egyik csúcsból kiindulva.
  - Az elválasztó halmaz mérete legfeljebb $2{\sqrt {2\cdot 18}}\approx 12$.

1. Eredmény:

  - Az elválasztó halmaz eltávolításával a gráf két részre osztható, amelyek mindegyike legfeljebb ${\frac {2\cdot 18}{3}}=12$ csúcsot tartalmaz.

Alkalmazások

1. Hálózati problémák:

  - Nagy gráfok hatékony felosztása kisebb részekre, például hálózati forgalom elemzésére.

1. Numerikus módszerek:

  - Síkgráfok particionálása mátrix-algoritmusok optimalizálására.

1. Adatstruktúrák és algoritmusok:

  - Hatékony gráfalgoritmusok tervezése, például gráfvágás vagy minimális vágás problémákhoz.

Összegzés

A síkgráf-elválasztási tétel azt mondja ki, hogy egy síkgráf csúcsai mindig kettéválaszthatók úgy, hogy a csúcsok száma az egyes részekben legfeljebb ${\frac {2n}{3}}$ legyen, és az elválasztó csúcsok száma arányosan kicsi maradjon. Ez a tétel fontos szerepet játszik a gráfelméletben és annak gyakorlati alkalmazásaiban, például hálózatok és algoritmusok tervezésében.

Fordítások

• angol: planar separator theorem (en)
• orosz: теорема о планарном разбиении (ru) (teorema o planarnom razbijenii)

További információk

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