Geometriai gráfelmélet

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 tágabb értelemben vett geometriai gráfelmélet (geometric graph theory) a gráfelmélet nagy kiterjedésű és amorf részterülete, ami mértani eszközökkel definiált gráfokkal foglalkozik. A szűkebb értelemben vett geometriai gráfelmélet geometriai gráfok és topológiai gráfok kombinatorikai és geometriai tulajdonságaival foglalkozik; a geometriai gráfok az euklideszi síkra (vagy más felületre) egyenes, de esetleg egymást metsző szakaszokkal (vagy általánosabban egyszerű görbeívvel) lerajzolt gráfok, míg a topologikus gráfok esetében az élek lerajzolása tetszőleges folytonos görbékkel történik. Így a geometriai gráfelmélet szűkebb értelemben „a geometriai és topologikus gráfok elmélete”.

Geometriai gráfok különböző típusai

Egy egyenes élű síkgráf olyan gráf, amelynek csúcsai az euklideszi síkba vannak ágyazva, élei pedig a sík egymást nem metsző egyenes szakaszai. A Fáry-tétel (1948) állítása szerint minden síkgráfhoz tartozik ilyen síkba ágyazás. Az egyenes élű síkgráfok speciális esetei a háromszögelések (sokszög háromszögekre bontása, ponthalmaz háromszögelése). Ezek maximálisak abban az értelemben, hogy nem lehetséges egyenes élekkel kiegészíteni őket. Még speciálisabb eset a Delaunay-háromszögelés: adott ponthalmaz Delaunay-háromszögelése olyan gráf, melyben két csúcs akkor van összekötve, ha létezik csak a két csúcsot tartalmazó kör.

Egy poliéder vagy politóp 1-váza a politóp csúcsainak és éleinek halmaza. Bármely konvex poliéder váza síkba rajzolható, és bármely k-dimenziós konvex politóp váza k-szorosan összefüggő. Megfordítva, a Steinitz-tétel kimondja, hogy minden 3-szorosan összefüggő síkbarajzolható gráf egy konvex poliéder váza; emiatt ezt a gráfosztályt poliédergráfoknak is nevezik.

Egy euklideszi gráf csúcsai a sík pontjai, az éleihez pedig éppen az él két csúcsa között mért távolságot rendeljük. Az euklideszi minimális feszítőfa egy euklideszi teljes gráf minimális feszítőfája. A távolságokat feltételként használva is lehet gráfokat definiálni; például egy egységtávolsággráfban a síkban egységnyi távolságra lévő csúcsok vannak összekötve. A Hadwiger–Nelson-probléma ilyen gráfok kromatikus számával foglalkozik.

Egy metszetgráf olyan gráf, melynek minden csúcsa egy halmaznak felel meg, és két csúcs akkor van összekötve, ha a hozzájuk tartozó halmazok metszete nem üres. Ha ezek a halmazok geometriai objektumok, az eredmény egy geometriai gráf. Például egy dimenzióban egyenes szakaszok metszetgráfja egy intervallumgráf; a síkban egységnyi körlapok metszetgráfja egységkörgráf. A körpakolási tétel szerint a nem metsző körök metszetgráfjai éppen a síkbarajzolható gráfok. A 2009-ben bizonyított Scheinerman-sejtés kimondja, hogy minden síkbarajzolható gráf előállítható a sík egyenes szakaszainak metszetgráfjaként.

Pontok és egyenesek egy geometriai konfigurációjának illeszkedési gráfjában minden csúcs a pontok és egyenesek valamelyikének felel meg, él pedig az illeszkedő pont-egyenes pároknak megfelelő csúcsok között húzódik. A projektív konfigurációk Levi-gráfjai számos fontos szimmetrikus gráfot és cage-et előállítanak.

Egy zárt sokszög láthatósági gráfjában két csúcs akkor van összekötve, ha a csúcsokat összekötő egyenes szakasz teljes egészében a sokszögön belül található. Nem ismert, hogy lehet hatékonyan ellenőrizni, hogy egy irányítatlan gráf előállítható-e láthatósági gráfként.

Egy parciális kocka (hiperkocka izometrikus részgráfja) olyan gráf, melynek csúcsai egy hiperkocka csúcsainak felelnek meg oly módon, hogy a gráfbeli távolságok megegyezzenek a hiperkocka csúcsai közötti Hamming-távolságokkal. Több fontos kombinatorikai struktúra, például egy gráf körmenter orientációi vagy hipersík-konfigurációk régiói közötti szomszédsági viszonyok kifejezhetők parciális kockagráf formájában. A parciális kockák fontos speciális esetei a permutaéderek (három dimenzióban ilyen a csonkított oktaéder), melyek rendezett objektumok permutációnak felelnek meg, éleik pedig a sorba rendezésnek megfelelő cseréket jelölik. Számos más fontos gráfosztály, köztük a mediángráfok definíciója is metrikus beágyazásokon alapul (Bandelt & Chepoi 2008).

A flip gráfok egyik fajtája az euklideszi sík egy ponthalmazának háromszögeléseiből formált gráf, melynek minden csúcsa egy háromszögelésnek felel meg, és két csúcs akkor van összekötve, ha a nekik megfelelő háromszögelés közti különbség éppen egy él cseréje egy másikra. A flip gráfok egyéb változataiban háromszögelés helyett négyszögekre vagy pszeudoháromszögekre osztás szerepel, esetleg magasabb dimenziószámú háromszögelések. Egy konvex sokszög háromszögeléseinek flip gráfja egy asszociéder (Stasheff-politóp) vázát alkotja. Egy ponthalmaz reguláris háromszögelésének (a magasabb dimenziójú konvex burkok projekcióinak) flip gráfja szintén előállhat váz formájában, ez az úgynevezett „másodlagos politóp”.

Kapcsolódó szócikkek

• Topologikus gráfelmélet
• Molekulagráf

Fordítás

• Ez a szócikk részben vagy egészben a Geometric 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.

Források

• Bandelt, Hans-Jürgen. Metric graph theory and geometry: a survey, Surveys on Discrete and Computational Geometry - Twenty Years Later, Contemporary Mathematics. American Mathematical Society, 49–86. o. (2008) 

• Towards a Theory of Geometric Graphs, Contemporary Mathematics. American Mathematical Society (2004) 

• Pisanski, Tomaž; Randić, Milan (2000. április 8.). „Bridges between geometry and graph theory”. Gorini, C. A. (Ed.) Geometry at Work: Papers in Applied Geometry: 174–194, Washington, DC: Mathematical Association of America. [2007. szeptember 27-i dátummal az eredetiből archiválva]. Hozzáférés: 2018. augusztus 23.