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.J.L. Gross and T.W. Tucker, Topological graph theory, Wiley Interscience, 1987 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.Graph topology, from PlanetMath. 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.
Példacikkek John Hopcroft és Robert Tarjan 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. 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 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
Jegyzetek
*