Síkbarajzolhatóság tesztelése
A gráfelméletben a síkbarajzolhatósági tesztelés problémája, egy algoritmikus probléma, annak tesztelésére, hogy egy adott gráf síkbarajzolható gráf-e (vagyis hogy rajzolható-e síkban úgy, hogy az élei metszenék egymást). Ez a számítástudományban egy jól körüljárt probléma, újszerű adatszerkezeteket használva gyors algoritmusok léteznek erre a problémára:.A legtöbb ilyen módszer O(n) idő alatt alkalmazható n csúcsú gráf esetén és időben aszimptotikus, lineáris. A síkbarajzolhatóság-tesztelési algoritmus kimenetének két értéke lehet, egy síkba ágyazott gráf, vagyis síkgráf, és, ha nem síkba rajzolható, akkor például egy Kuratowski részgráf.
Síkba rajzolhatósági kritériumok
szerkesztésA síkbarajzolhatósági tesztelési algoritmusok jellemzően kihasználják azokat a tételeket a gráfelméletben, amelyek a síkbeli gráfok halmazát a gráfrajzoktól függetlenül jellemzik. Ezek pedig a:
- Kuratowski-tétel, miszerint egy véges gráf akkor és csak akkor rajzolható síkba, ha nem tartalmaz olyan részgráfot, amely topologikusan izomorf K5-tel (az ötcsúcsú teljes gráffal) vagy K3,3-mal (az ún. három ház–három kút gráffal.
- Wagner-tétel, miszerint egy síkgráf akkor és csak akkor síkba rajzolható, ha sem a K5, sem a K3,3 nem minora.
- A Fraysseix–Rosenstiehl síkbarajzolhatósági kritérium, amely jellemzi a síkgráfot az élek bal és jobb oldali rendezése alapján, a mélységi keresési fában(depth-first search tree).
A Fraysseix–Rosenstiehl síkbarajzolhatósági kritérium közvetlenül felhasználható a síkbarajzolhatóság tesztelésére szolgáló algoritmusok részeként, míg a Kuratowski és a Wagner tétele közvetett módon alkalmazható: ha egy algoritmus egy adott gráfon belül megtalálja a K 5 vagy K 3,3 másolatát, akkor egy adott gráfon belül biztos lehet abban, hogy a bemeneti gráf nem síkgráf,ezt adja vissza további számolások nélkül.
Más síkbarajzolhatósági kritériumok, amelyek matematikailag jellemzőek, de a síkba rajzolhatósági tesztelési algoritmusok szempontjából kevésbé fontosak:
- A Whitney síkbarajzolhatósági kritérium, miszerint egy gráf sík, akkor és csak akkor, ha a grafikus matroidja szintén grafikus.
- A Mac Lane síkbarajzolhatósági kritérium a véges síkbeli gráfokat a körterei alapján jellemzi.
- A Schnyder-tétel, amely a síkgráfokat egy társított, parciális rendezés dimenziója alapján jellemzi, és
- Colin de Verdière síkbarajzolhatósági Colin de Verdière-gráfinvariáns kritériuma a spektrális gráfelmélet alapján dolgozik.
Algoritmusok
szerkesztésTovábbi útvonalak
szerkesztésA Hopcroft és Tarjan klasszikus útvonal-összeadási módszere[1] volt az első, amely 1974-ben közzétett egy lineáris idejű, síkbarajzolhatósági tesztelési algoritmust. A Hopcroft és Tarjan algoritmusa megtalálható a Library of Efficient Data types and Algorithms könyvben, Mehlhorn, Mutzel és Näher[2][3][4] szerzőktől. 2012-ben Taylor kibővítette ezt az algoritmust, hogy előállítsa a ciklikus élrendezés minden permutációját a kétszeresen összefüggő komponensek síkbeli beágyazásához.
A csúcshozzáadás módszere
szerkesztésA csúcshozzáadási módszerek úgy működnek, hogy bemutatják az adott gráf, indukált részgráfjának lehetséges beágyazódását ábrázoló adatszerkezetet, és a csúcsokat egyenként adják hozzá ehhez az adatszerkezethez. Ezek a módszerek egy nem hatékony O (n2) módszerrel kezdődtek, ezeket Lempel, Even és Cederbaum dolgozta ki 1967-ben.[5] Ezt fejlesztették tovább Even és Tarjan, akik lineáris idejű megoldást találtak az s, t- számozására[6] valamint Booth és Lueker, akik kidolgozták a PQ fa adatstruktúráját. Ezekkel a fejlesztésekkel az időtartam lineáris futású, és gyakorlatban túlszárnyalja a csúcs hozzáadási módszert. Ezt a módszert kiterjesztették arra is, hogy a síkba ágyazás (rajz) hatékonyan kiszámítható legyen egy síkgráfra.[7] 1999-ben Shih és Hsu leegyszerűsítette ezeket a módszereket a PC-fa (a PQ-fa gyökérzet nélküli változata) és a csúcsok mélységi keresési fájának postorder-bejárásával.[8]
Az élhozzáadás módszere
szerkesztésJohn Boyer és Wendy Myrvold[9] 2004-ben kifejlesztett egy egyszerűsített O (n) algoritmust, amelyet eredetileg a PQ fa módszer ihletett, amely megszabadul a PQ fától és élek hozzáadását használja, ha lehetséges, a síkba ágyazás kiszámításához. Ellenkező esetben Kuratowski alcsoportot ( hogy nem K 5 vagy K 3,3 ) néz. Ez az egyike a manapság legkorszerűbb két algoritmusnak (a másik a de Fraysseix, de Mendez és Rosenstiehl síkba rajzolhatósági tesztelési algoritmus[10][11] ). Lásd még a [12] a kísérleti összehasonlítást a Boyer és a Myrvold síkbarajzolhatósági-teszt előzetes verziójával. Ezenkívül a Boyer – Myrvold tesztet használják arra, hogy egy nem síkbeli bemeneti gráfból, több Kuratowski algráfot keressenek egy futási időben, a kimeneti méret függvényében.[13] A síkbarajzolhatósági vizsgálat[14][15] és a több Kuratowski algráf kinyerésének forráskódja nyilvánosan elérhető. Azt az algoritmust, amely megmutatja a Kuratowski-algráfot a csúcsok lineáris idejében, Williamson fejlesztette ki az 1980-as években.[16]
Felépítési sorrend módszer
szerkesztésEz egy másik módszer, ami a 3 összeköttetésű (triconnected) gráfok induktív konstrukcióját alkalmazza, a G minden 3 összeköttetésű összetevőjének, síkbeli beágyazásának fokozatos létrehozására (és ennélfogva a G síkba ágyazására).[17] A felépítés K4-gyel kezdődik, oly módon, hogy minden közbenső gráf, amely a teljes felépítés felé vezet, ismét 3 összeköttetésű legyen. Mivel az ilyen gráfoknak egyedi beágyazása van (a flippelésig és a külső oldal megválasztásáig), a következő nagyobb gráfnak, ha még mindig sík, a korábbi gráf finomításának kell lennie. Ez lehetővé teszi a síkbarajzolhatósági tesztet úgy, hogy minden egyes lépést teszteljen arra, hogy a következő hozzáadott élnek megvan-e mindkét vége, rendelkezik-e beágyazással. Noha ez fogalmi szempontból nagyon egyszerű (és lineáris futási időt ad), maga a módszer szenved a szerkesztési sorrend bonyolultságától.
Jegyzetek
szerkesztés- ↑ Hopcroft, John & Tarjan, Robert E. (1974), "Efficient planarity testing", Journal of the Association for Computing Machinery 21 (4): 549–568, DOI 10.1145/321850.321852
- ↑ Mehlhorn, Kurt & Mutzel, Petra (1996), "On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm", Algorithmica 16 (2): 233–242, DOI 10.1007/bf01940648
- ↑ Mehlhorn, Kurt & Mutzel, Petra (1993), An Implementation of the Hopcroft and Tarjan Planarity Test and Embedding Algorithm
- ↑ Mehlhorn, Kurt & Näher, Stefan (1995), "LEDA: A library of efficient data types and algorithms", Communications of the ACM 38 (1): 96–102, DOI 10.1145/204865.204889
- ↑ Lempel, A.; Even, S. & Cederbaum, I. (1967), "An algorithm for planarity testing of graphs", in Rosenstiehl, P., Theory of Graphs, New York: Gordon and Breach, pp. 215–232.
- ↑ Even, Shimon & Tarjan, Robert E. (1976), Computing an st-numbering, pp. 339–344.
- ↑ Chiba, N.; Nishizeki, T. & Abe, A. (1985), A linear algorithm for embedding planar graphs using PQ–trees, pp. 54–76.
- ↑ Shih, W. K. & Hsu, W. L. (1999), A new planarity test, pp. 179–191.
- ↑ On the cutting edge: simplified O(n) planarity by edge addition, <http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf>.
- ↑ Trémaux Trees and Planarity.
- ↑ The left-right planarity test, <http://www.inf.uni-konstanz.de/algo/publications/b-lrpt-sub.pdf>.
- ↑ Proc. 11th Int. Symp. Graph Drawing (GD '03)
- ↑ Proc. 15th Int. Symp. Graph Drawing (GD'07).
- ↑ OGDF - Open Graph Drawing Framework: Start
- ↑ Boost Graph Library: Boyer-Myrvold Planarity Testing/Embedding - 1.40.0
- ↑ Depth First Search and Kuratowski Subgraphs
- ↑ Schmidt, Jens M. (2014), Automata, Languages, and Programming, vol. 8572, Lecture Notes in Computer Science, ISBN 978-3-662-43947-0, DOI 10.1007/978-3-662-43948-7_80
Fordítás
szerkesztésEz a szócikk részben vagy egészben a Planarity testing című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.