Gamma algoritmus

A gamma-algoritmus  egy olyan algoritmus, amely egy gráf síkba helyezésére és a síkság ellenőrzésére szolgál .

Definíciók

• A Γ gráf egy szakasza a H részgráfhoz képest , amely  a G\H gráf összefüggő komponense.
• A szegmens megengedett lapja az összes érintkezési csúcsot tartalmazó H gráf lapja.
• A H részgráf Г gráf S szakaszának érintkezési csúcsa S és H bármely csúcsa .
• A szegmens gamma-lánca minden olyan lánc, amely nem ismétlődik a csúcsok között, és amely pontosan két érintkezési csúcsot tartalmaz - az elejét és a végét.

Algoritmus

Fektesse a síkra a G gráf tetszőleges H ciklusát csúcsok ismétlődése nélkül.

1. Szerkesszük meg a G gráf összes S 1 ,..,S k szegmensét H -ból .
2. Ha van egy S i szegmens egy megengedett lappal  , jelölje ki.
3. Ha minden szegmensnek több további lapja is van, válassza ki bármelyiket.
4. Válasszon ki egy tetszőleges gamma-láncot a szegmensből, és illessze egy megengedett lapba.
5. Folytassa a (2) lépéssel egy gamma lánc hozzáadásával a H gráfhoz .

A gráfok tulajdonságai az algoritmus helyes működéséhez

1. A grafikont össze kell kapcsolni .
2. A grafikonnak legalább egy ciklusnak kell lennie .
3. A gráfnak ne legyenek hidak , azaz élek, amelyek eltávolítása után a gráf két összefüggő komponensre bomlik .

Ha az (1) tulajdonság sérül, akkor a grafikont külön kell halmozni a csatlakoztatott összetevők szerint. Ha a (2) tulajdonság sérül, akkor a gráf egy fa, és triviális annak simítását megrajzolni.

A tulajdonjog megsértése (3) esetét részletesebben tárgyaljuk. Ha vannak hidak a grafikonon, akkor azokat le kell vágni, minden egyes összekapcsolt komponenst külön-külön le kell lapítani, majd hidakkal összekötni. Itt egy nehézség adódhat: a fektetési folyamat során a híd végpontjai egy síkgráfon belül lehetnek. Rajzoljunk egy összekapcsolt komponenst, és sorban adjunk hozzá továbbiakat. Minden egyes új összekapcsolt komponens a megfelelő híd végcsúcsát tartalmazó lapra rajzolódik. Mivel az összekapcsolt komponensek hídjain keresztüli kapcsolódási grafikon egy fa, így sík tömítést kaphatunk.

Tétel

A Г gráf akkor és csak akkor síkbeli, ha a gamma-algoritmus a síkra helyezi.

Bizonyítás

Az ellenkező irányba a bizonyíték nyilvánvaló.

Bizonyítsuk be. Ha a Γ gráf sík, akkor a síkon elhelyezett H részgráf kiegészíthető a Γ gráf fektetésével . Ez különösen az utolsó lépésnél azt jelenti, hogy a Γ gráf teljesen el van helyezve a síkon.

Legyen a Γ gráf síkbeli. Ekkor a Γ gráf bármely ciklusa halmozottan sokszögként jelenik meg. Ez a sokszög benne van a Γ gráf síkon történő elhelyezésében.

Legyen igaz az állítás az algoritmus n-edik iterációjáig.

Lehetőségek:

1. S illeszkedik a H gráf egyetlen lapjába, a H gráf a G gráf hajtásáig teljesedik , és ebben a hajtásban az S szegmens az egyetlen lapjában található. Következésképpen az S szakasz bármely C gammaútjának beágyazása ebbe a lapba a H gráf C -vel való egyesüléséhez vezet , amely kiterjeszthető a Г csempézésre.
2. Minden szegmensnek több érvényes lapja van.

Legyen S egy F 1 és F 2  megengedett lapokkal rendelkező szakasz . A H részgráfot az induktív hipotézis kiegészíti a Г gráf lefektetésével . Ebben az esetben az S szegmens az egyik megengedett lapba illeszkedik. Az általánosság elvesztése nélkül legyen ez az arc F 1 . Bizonyítsuk be, hogy van H kiterjesztése a Г gráf fektetéséig, amelyben az S szakasz az F 2 lapban fekszik . Mivel F 1 és F 2  további lapok, mindkettő tartalmazza az S szegmens összes érintkezési csúcsát . Ezért az S szakasz összes érintkezési csúcsa az F 1 és F 2 közös csúcsok halmazában található . Legyen S 1 ,..,S k az F 1  -ben foglalt összes szegmens . Legyen S ' 1 ,..,S ' m  minden olyan szegmens az F 2 -ben , amely az egyik csúcsot tartalmazza. Legyen az S ' i szegmensnek egy érintkezési csúcsa és egy másik érintkezési csúcsa, amely nem tartozik F 1 - hez . Ekkor a megengedett S ' i lapok az F 2 lapok , és ez a (2) pont feltételezése. Az ellentmondásból következik, hogy minden S ' i érintkezési csúcs (hasonlóan S i -hez) az S ' 1 ,..,S ' m szegmensek csúcsainak halmazában található .

Ezért a G gráf fektetésénél lehetőség van az S 1 ,..,S k szegmensek F 2 -re , valamint az S ' 1 ,..,S ' m szegmensek F 1 -re való mozgatására , ez vezet a fektetéshez. a Г gráfnak , amelyben az S szakasz az F 2 lapban fekszik .

Ezért az algoritmus bármilyen sík gráfot illeszt a síkra. Amire szükség is volt.

Lásd még

• Grafikon
• Síkgrafikon
• gráfelmélet
• A gráfelmélet szószedete

Irodalom

• Irinev Anton, Kashirin Viktor Algoritmus gráfok lapos halmozására [1]
• Novikov IA Diszkrét matematika programozóknak: Tankönyv egyetemeknek. 3. kiadás - Szentpétervár: Péter, 2009. - 384 e .: ill. — ("Tankönyv az egyetemeknek" sorozat), ISBN 978-5-91180-759-7
• Nefedov V. N., Osipova V. A. A diszkrét matematika tanfolyama: Proc. pótlék.-M.; MAI Kiadó, 1992.—264 s: ill., ISBN 5-7035-0157-X