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[szerkesztés]
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[szerkesztés]
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[szerkesztés]
- Metszési szám (gráfelmélet)
- Nemszám (génusz)
- Síkbarajzolható gráf
- Tóruszra rajzolható gráf
- Topologikus kombinatorika
Fordítás[szerkeszté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[szerkesztés]
- ↑ 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).