Topologikus gráfelmélet

Ez a cikk a gráfbeágyazásokkal foglalkozik. A metsző élekkel síkba rajzolt gráfokat lásd a topologikus gráf szócikkben

A gráfelmélet kezdeti fejlődését jellemzően topológiai és mértani témák motiválták, gondoljunk a königsbergi hidak problémájára, az Euler-féle poliédertételre vagy a síkba rajzolhatóság Kuratowski-tételére. Csak a 20. század második felében terjedt el a gráfok mértani objektumok helyett absztrakt, binér relációként való kezelése. Bár ez az absztrakció sok területen (Ramsey-elmélet, extremális gráfelmélet, algebrai gráfelmélet stb.) gyümölcsözőnek bizonyult, a geometriai alkalmazásokra nem minden esetben tudott megfelelő válaszokkal szolgálni.

A topologikus gráfelmélet a matematika, azon belül a gráfelmélet területén gráfok felületekbe ágyazásait és térbeli beágyazásait, valamint a gráfokat mint topologikus tereket tanulmányozza.^[1] Ezen kívül gráfok immerziójával is foglalkozik.

Egy gráf felületbe ágyazása más néven egy gráf felületre (például gömbfelszínre) rajzolását jelenti oly módon, hogy a gráf élei ne messék egymást. Közismert fejtörő a témában a három ház–három kút-probléma. Az alkalmazások közé tartozik az elektronikus áramkörök nyomtatása, ahol a cél egy áramkör (a gráf) áramköri lapra való nyomtatása (beágyazása) anélkül, hogy a huzalok érintkezése miatt rövidzár jöjjön létre.

Gráfok mint topologikus terek

Adott irányítatlan gráfhoz hozzárendelhető egy C absztrakt szimpliciális komplexum (a "complex" szó téves fordítása miatt sokan hívják komplexusnak), melyben a csúcsokhoz egyelemű, az élekhez kételemű halmaz tartozik.^[2] A |C| komplexum mértani megvalósítása úgy történik, hogy minden élhez a [0,1] egységintervallum egy kópiája csatolódik, ahol az intervallumok végpontjai a csúcsokhoz vannak ragasztva. Ebből a szemszögből mind a gráfok felületbe ágyazásai, mind más gráfok felosztásaiként való beágyazásai tekinthetők topologikus beágyazások eseteinek; a gráfok homeomorfizmusai a topologikus homeomorfizmusok speciális esetei; az összefüggő gráf koncepciója egybeesik a topologikus összefüggőséggel és egy összefüggő gráf pontosan akkor fa, ha fundamentális csoportja triviális.

Gráfokhoz kötődő szimpliciális komplexum továbbá a klikk-komplexum, melyben a gráf klikkjeihez tartozik egy-egy halmaz vagy a párosítási komplexum, melyben a gráf párosításaihoz tartozik-egy-egy halmaz (ezzel ekvivalens az élgráf komplementerének klikk-komplexuma). Egy teljes páros gráf párosítási komplexumát „sakktáblakomplexumnak” (chessboard complex) is nevezik, mivel leírható egy sakktáblán egymást nem támadó bástyák halmazai komplexumaként.^[3]

Példacikkek

John Hopcroft és Robert Tarjan^[4] kitaláltak egy olyan módszert a gráfok síkba rajzolhatóságának tesztelésére, mely az élek számát tekintve lineáris időt vesz igénybe. Algoritmusuk egy „pálmafának” nevezett gráfbeágyazást konstruál meg. A hatékony síkba rajzolhatósági tesztelés alapvető fontosságú a gráflerajzolás területén.

Fan Chung és tsai.^[5] a gráfok könyvbe ágyazását tanulmányozták, melyben a gráf csúcsai a könyv gerincének egyenesén helyezkednek el, a gráf élei pedig úgy helyezkednek el a könyv lapjain, hogy az egy-egy lapra rajzolt élek ne messék egymást. Ez a probléma a többrétegű nyomtatott áramköri lapok áramkör-kiosztásának megtervezésekor előkerülő problémák absztrakciója.

A gráfbeágyazásokat a gráfminorelméleten és a gráfminor-tételen keresztül gráfszerkezeti eredmények bizonyítására is felhasználták.

Kapcsolódó szócikkek

Fordítás

Ez a szócikk részben vagy egészben a Topological graph theory 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.

Jegyzetek

↑ J.L. Gross and T.W. Tucker, Topological graph theory, Wiley Interscience, 1987
↑ Graph topology, from PlanetMath.
↑ Sablon:Cite arxiv
↑ (1974) „Efficient Planarity Testing”. Journal of the ACM 21 (4), 549–568. o. DOI:10.1145/321850.321852.
↑ (1987) „Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design”. SIAM Journal on Algebraic and Discrete Methods 8 (1).

[1] J.L. Gross and T.W. Tucker, Topological graph theory, Wiley Interscience, 1987

[2] Graph topology, from PlanetMath.

[3] Sablon:Cite arxiv

[4] (1974) „Efficient Planarity Testing”. Journal of the ACM 21 (4), 549–568. o. DOI:10.1145/321850.321852.

[5] (1987) „Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design”. SIAM Journal on Algebraic and Discrete Methods 8 (1).

[1]

[2]

[3]

[4]

[5]