Wikipédia

Duális gráf

speciális gráf
Ez a közzétett változat, ellenőrizve: 2022. november 10.

A matematika, azon belül a gráfelmélet területén a G síkgráf duális gráfja az a G* gráf (multigráf), mely a következő módon állítható elő. G* csúcsai az eredeti G síkgráf tartományai; ha két G-beli tartományt egy él választ el egymástól, G*-ban él húzódik (ha a tartományok több él mentén voltak szomszédosak, akkor többszörösen is), ha az él mindkét oldalán ugyanaz a tartomány jelenik meg, akkor pedig hurokél. Tehát minden G-beli e élnek létezik G*-beli, duális megfelelője, melynek végpontjai az e két oldalán lévő tartományoknak megfelelő duális csúcsok. A duális gráf meghatározása függ G síkba ágyazásától, tehát a duális gráf a síkgráf (egy konkrét síkba rajzolás) sajátja, nem pedig a síkbarajzolható gráfé (melynek több síkba rajzolása is létezhet). Egy síkbarajzolható gráfnak tehát több duálisa is létezhet, a konkrét síkba rajzolástól függően. Más szavakkal: bár a síkbaágyazható gráf egy konkrét beágyazásához tartozó duálisok egyediek (izomorfia erejéig), egy gráfnak létezhetnek különböző (nem izomorf) duálisai, melyek különböző (nem homeomorf) beágyazásaiból származnak. Síkgráf duálisa is síkbarajzolható.[1]

A piros gráf a kék gráf duálisa, és viszont.

Történelmileg a gráfok dualitását elsőként a szabályos testek közötti dualitási viszonyaiban ismerték fel. A gráfok dualitása a duális poliéderek és tesszellációk topologikus általánosítása, melyek további, algebrai általánosítása a matroid duálisának fogalma. A síkgráfok dualitásának különböző változatai közé tartoznak az irányított gráfok duálisai, valamint a síktól eltérő kétdimenziós felületekbe beágyazott gráfokra értelmezett dualitások. Ezeket azonban meg kell különböztetni a gráfok teljesen más jellegű él–csúcs-duálisaitól, melyeket élgráfoknak neveznek.

Azért használjuk a „duális” kifejezést, mert a dualitási tulajdonság szimmetrikus, azaz ha H gráf az összefüggő G gráf duálisa, akkor G gráf is duálisa a H gráfnak. A duális gráfok azért is hasznosak, mert szerkezetük és számos tulajdonságuk egyszerű módon kapcsolódik az eredeti gráf jellemzőihez; így egyes gráfokkal kapcsolatos eredmények bizonyíthatók úgy is, ha a gráfok duálisait vesszük alapul.

Jó példa erre a kör–vágás-dualitás: azaz a duális gráfban a vágások felelnek meg az eredeti gráf köreinek és fordítva. A feszítőfák duálisai a feszítőfák komplementereivel egyeznek meg.[2] Az egyszerű gráfok (párhuzamos és hurokélek nélküli gráfok) duálisai pedig a 3-szorosan élösszefüggő gráfok

A duális gráfok segítenek megérteni az útvesztők és vízgyűjtő területek szerkezetét is. Fontos alkalmazásaik vannak többek között a számítógépes látás, számítási geometria, a hálógenerálás és az integrált áramkörök tervezésének területein.

Példák

szerkesztés

Körök és dipólusok

szerkesztés

Egy körgráf egyedi síkbarajzolása a Jordan-féle görbetétel értelmében a síkot mindössze két tartományra osztja, a körön belül, illetve kívül eső területre. Mivel azonban a   kör esetén a két régiót n különböző él választja el egymástól, a   duálisa egy két csúcsból (a tartományok duálisaiból) és a köztük húzódó n duális élből álló multigráf. Az ilyen gráfot dipólusgráfnak nevezzük. Megfordítva, az n-élű dipólusgráf duálisa a   körgráf.[3]

Önduális gráfok

szerkesztés
 
Egy önduális gráf

Egy síkgráf akkor önduális, ha saját duálisával izomorf. Az önduális poliéderekből (konkrétan gúlákból) származtatható kerékgráfok önduális gráfok végtelen családját alkotják.[4][5] Léteznek azonban önduális, azonban nem poliéderből származó gráfok, mint amilyen az ábrán is látható. (Servatius & Christopher 1992) leírnak két gráfműveletet, melyekkel adott síkbarajzolható gráfot tartalmazó önduális gráf szerkeszthető: ezek a „tapasztás” és „robbantás” (adhesion and explosion); például az ábrán szereplő önduális gráf megszerkeszthető tetraéder és annak duálisa összetapasztásával.[5]

Az Euler-formulából adódóan minden n csúcsú önduális gráfnak pontosan 2n − 2 éle van.[6] Minden egyszerű önduális síkgráf legalább négy, három fokszámú csúcsot tartalmaz, és minden önduális síkbarajzolás legalább négy háromszögű tartománnyal rendelkezik.[7]

Tulajdonságok

szerkesztés

A gráfelmélet természetesen adódó és fontos fogalmai sok esetben ugyanolyan természetesen, de más formában jelentkeznek a duális gráfban. Mivel egy összefüggő síkgráf duálisának duálisa az eredeti gráffal izomorf,[8] ezek a párosítások mindig kétirányúak: ha a síkgráf X fogalma a duálisban Y fogalomnak felel meg, akkor a síkgráf Y fogalma éppen a duális X fogalmának felel meg.

Egyszerű gráfok / multigráfok

szerkesztés

Egyszerű gráf duálisa nem feltétlenül egyszerű: tartalmazhat hurokéleket (olyan él, melynek mindkét végpontja ugyanazon a csúcson van), valamint két csúcsát több él is összekötheti, ami a körgráfok és dipólus-multigráfok dualitásából is nyilvánvaló. A lent részletesebben kifejtett vágás–kör-dualitás speciális eseteként a G síkbarajzolható gráfban található elválasztó élek (hidak) egy az egyben megfeleltethetők G duálisának hurokéleivel.[9] Hasonló okból a duális multigráfban szereplő párhuzamos élpár (tehát egy 2 hosszúságú kör) az eredeti gráf 2 élből álló vágás-élhalmazának felel meg (olyan élpár, melynek törlése után szétesik a gráf). Ezért egy síkbarajzolható gráf pontosan akkor egyszerű, ha duálisában nem találhatók 1 vagy 2 élből álló vágás-élhalmazok, tehát ha 3-szorosan élösszefüggő. Azok a síkbarajzolható egyszerű gráfok, melyek duálisa is egyszerű, a 3-szorosan élösszefüggő, síkbarajzolható egyszerű gráfokkal egyeznek meg.[10] Ez a gráfosztály magában foglalja a 3-szorosan összefüggő, síkbarajzolható egyszerű gráfokat, de nem egyezik meg velük. Például az ábrán látható önduális gráf 3-szorosan élösszefüggő (ezért duálisa egyszerű gráf), de nem 3-szorosan összefüggő.

Egyediség

szerkesztés
 
Mindkét piros gráf a kék gráf duálisa, mégsem izomorfak

Mivel a gráf duálisának konstrukciója a gráf konkrét felületbe ágyazásának függvénye, ezért a síkbarajzolható gráf duálisa nem egyedi abban az értelemben, hogy ugyanannak a síkbarajzolható gráfnak több, egymással nem izomorf duálisa is létezhet.[11] Az ábrán a kék gráfok izomorfak, de piros duálisaik nem. Ez könnyen belátható, hiszen a felső piros duális gráf rendelkezik egy 6 fokszámú csúccsal (ami a kék gráf külső tartományának felel meg), míg az alsó piros duális gráf összes csúcsának 6-nál kisebb a fokszáma.

Hassler Whitney megmutatta, hogy ha egy gráf 3-összefüggő, akkor a síkbarajzolása (izomorfia erejéig) egyedi, így a duálisa is az.[12] A Steinitz-tétel értelmében ezek a gráfok éppen a poliédergráfok, a konvex testek élváza által meghatározott gráfok. Egy síkbarajzolható gráf pontosan akkor 3-összefüggő, ha duálisa is az. Általánosabban, egy síkbarajzolható gráf pontosan akkor rendelkezik egyedi síkbarajzolással, és így egyedi duálissal, ha egy 3-csúcsösszefüggő síkbarajzolható gráf felosztásával (egyes élek úttá alakításával) előállítható. Léteznek olyan síkbarajzolható gráfok is, ilyen például a K2,4 teljes páros gráf, melyek bár nem 3-összefüggők, síkbarajzolásaik mégis egymással izomorfak. Természetesen a duális gráfok ilyenkor is izomorfak.

Mivel különböző lerajzolások különböző duálisokhoz vezethetnek, a konkrét lerajzolások ismerete nélkül annak eldöntése, hogy egy gráf duálisa-e a másiknak, nem triviális probléma. Kétszeresen összefüggő gráfokon polinom időben megoldható a gráfok SPQR-fája segítségével: a közös duálissal rendelkezés ekvivalenciarelációja kanonikus alakjának megalkotásával. Például az illusztráció két piros gráfja ekvivalens ezen reláció szerint. A nem 2-összefüggő gráfok esetében ez a reláció nem ekvivalenciareláció, így a kölcsönös dualitás problémájának tesztelése NP-teljes probléma.[13]

Vágások és körök

szerkesztés

Egy összefüggő gráfon értelmezett vágás élhalmaza a gráf éleinek halmazából azokat az éleket tartalmazza, melyeknek a csúcsok kétfelé particionálásakor a két végpontjuk különböző partícióban (a vágás más-más oldalán) található. A vágás élhalmazába tartozó élek eltávolítása után tehát a gráf szükségképpen legalább két összefüggő komponensre esik szét. Egy minimális vágás-élhalmaz (bond) tulajdonsága, hogy pontosan két komponensre osztja a gráfot, és valódi részhalmazai már nem alkotnak vágási élhalmazt.[14] Egy egyszerű kör olyan összefüggő részgráf, melyben a kör minden csúcsa a kör pontosan két élére illeszkedik.[15]

Ha G síkbarajzolható összefüggő gráf, akkor G minden egyszerű köre megfelel G duálisában egy minimális vágási élhalmaznak, és viszont.[16] Ez a Jordan-féle görbetétel egy változatának is tekinthető: minden egyszerű kör szétválasztja G tartományait a kör belsejében lévő, illetve a körön kívül eső tartományokra, a kör éleinek duálisai pedig pontosan azok az élek, melyek a kör belseje és a körön kívül eső rész között húzódnak.[17] Egy síkbarajzolható gráf bősége (legkisebb körének mérete) megegyezik duálisának élösszefüggőségével (legkisebb vágás-élhalmazának méretével).[18]

Ez a dualitás az egyedi vágás-élhalmazokról és körökről kiterjeszthető az általuk meghatározott vektorterekre is. Egy gráf körtere megegyezik az összes, minden csúcsában páros fokszámmal rendelkező részgráfjai által alkotott családdal; ez úgy is tekinthető, mint a GF(2) véges test fölötti vektortér, ahol a két élhalmaz közötti szimmetrikus differencia a vektortér vektor-összeadási műveleteként működik. Hasonlóan, a gráf vágástere az összes vágás-élhalmaz családja, hasonlóan definiált vektor-összeadási művelettel. Ekkor egy síkbarajzolható gráf körtere és duálisának vágástere egymással izomorf vektorterek.[19] Következésképpen, egy síkbarajzolható gráf rangja (vágásterének Hamel-dimenziója) megegyezik duálisának ciklikus rangjával (körterének dimenziójával) és viszont.[11] Egy gráf körbázisa olyan egyszerű körök halmaza, melyek a körtér bázisát alkotják (minden páros fokú részgráf egyféleképpen állítható elő ilyen körök szimmetrikus differenciájával). Súlyozott, de irányítatlan síkbarajzolható gráfok (kellően általános súlyokkal, hogy a gráf ne tartalmazzon két azonos súlyú kört) esetén a gráf minimális súlyú körbázisa a duális gráf Gomory–Hu-fájával egyezik meg, ami az egymásba ágyazott vágások olyan gyűjteménye, melyek együtt a gráf minden csúcspárját szétválasztó minimális vágásokat is magukban foglalják. A minimális súlyú körbázis minden köre magában foglalja olyan élek halmazát, melyek a Gomory–Hu-fa valamely vágás-élhalmazának duálisai. Ha megengedjük a körök súlyainak egyenlőségét, a minimális súlyú körbázis nem feltétlenül egyedi, de ebben az esetben is igaz, hogy a duális gráf Gomory–Hu-fája megfelel a gráf valamely minimális súlyú körbázisának.[19]

Irányított síkbarajzolható gráfok esetén az egyszerű irányított körök duálisai az irányított vágások (a csúcsok particionálása két csúcshalmazba oly módon, hogy minden él egy irányba mutasson, az egyik csúcshalmazból a másik felé). Az erősen irányított síkbarajzolható gráfok (melyekben a gráf irányítatlan, orientálás előtti változata összefüggő, és minden él egy körhöz tartozik) az irányított körmentes gráfok duálisai, melyekben egyetlen él sem tartozik körhöz. Más megfogalmazásban, egy összefüggő, síkbarajzolható gráf erős irányításai (az élekhez olyan irányok rendelése, melyek erősen összefüggő gráfot eredményeznek) a körmentes irányítások duálisai (az élekhez olyan irányok rendelése, melyek irányított körmentes gráfot eredményeznek).[20]

Feszítőfák

szerkesztés
 
Egyszerű labirintus, melyben a falak és a falak közötti folyosók két egymásba kapcsolódó fát alkotnak.

Egy gráf feszítőfája a definíció szerint a gráf összes csúcsát tartalmazza, élei az eredeti gráf élei közül valók, és összefüggő körmentes részgráfot alkot. A vágás–kör-dualitás okán, ha a G síkbarajzolható gráf S élhalmaza körmentes, akkor az S duálisának élhalmaza nem tartalmaz vágást, amiből következik, hogy a duális élek komplementer halmaza összefüggő részgráfot alkot. A szimmetria miatt, ha S összefüggő, akkor az S komplementere duálisának élei körmentes részgráfot alkotnak. Az előzőek szerint, ha S mindkét tulajdonsággal rendelkezik – összefüggő és körmentes – ugyanez igaz a duális gráf komplementerére. Tehát G minden feszítőfája a duális gráf egy feszítőfájának komplementere, és viszont. Így bármely síkgráf, illetve duálisának élei együtt (általában többféleképpen) két, az eredeti, illetve a duálisban található feszítőfába particionálhatók oly módon, hogy együtt a gráf minden minden csúcsát és tartományát elérjék, de ne messék egymást. Továbbá, G minimális feszítőfája a duális gráf maximális feszítőfájának komplementere.[21] A legrövidebb utak fái esetében hasonló módszer nem alkalmazható; a két feszítőfa átmérője nagyon különböző lehet: léteznek olyan síkgráfok, melyekben minden feszítőfa-duális komplementer feszítőfa pároshoz legalább két olyan fa tartozik, melyek távolságai szignifikánsan meghaladják a gráfbeli távolságokat.[22]

Az ilyen, egymásba kapcsolódó fákba történő felbontás megfigyelhető egyes útvesztők ábrázolásaiban, melyek egyetlen bejárattal és összefüggő fallal rendelkeznek. Ebben az esetben a labirintus falai és a falak közötti terület is matematikailag fa formát ölt. Ha a labirintus üres részét cellákra osztjuk fel (pl. négyzetrács), akkor ez a felosztás egy síkbarajzolható gráf beágyazásának tekinthető, melyben a falak fastruktúrája a gráf feszítőfája, míg az üres terület feszítőfája a duális gráf feszítőfáját alkotja.[23] Hasonló egybe fonódó fa-párok láthatók a vízgyűjtő területek folyamainak és folyóinak, valamint az őket elválasztó duális gerincvonalak rajzolatában.[24]

Az élek és duálisaik két fába particionálhatósága könnyű bizonyítását adja az Euler-formula síkgráfokra vonatkozó változatának, miszerint V − E + F = 2, ahol V a csúcsok, E az élek, F pedig a tartományok száma. Bármely feszítőfa és komplementer duális feszítőfája az éleket két, V − 1, illetve F − 1 részhalmazra particionálja, a két részhalmaz méretét az egyenlőséghez adva

E = (V − 1) + (F − 1)

már az Euler-formulára átrendezhető kifejezést kapunk. Duncan Sommerville szerint az Euler-formula ezen bizonyítását először G. K. C. Von Staudt jegyezte fel: Geometrie der Lage (Nürnberg, 1847).[25]

A síktól eltérő felületbe ágyazáskor a feszítőfa komplementeréhez duális élek halmaza nem ad ki duális feszítőfát. Ehelyett a duális feszítőfának néhány extra éllel való unióját adja; a plusz élek számát a felület génusza határozza meg, amibe a gráf beágyazásra került. Az extra élek a feszítőfák útjaival együtt felhasználhatók a felület fundamentális csoportjának generálására.[26]

További jellemzők

szerkesztés

Bármely, síkgráfokra vonatkozó képlet, ami csúcsokra és tartományokra hivatkozik, átalakítható a duális gráfban érvényes, ekvivalens képletté, melyben a csúcsok és tartományok meg vannak cserélve. Az önduális Euler-formula ennek csak egy példája. A Harary által megadott, a kézfogás-lemmára épülő példa szerint bármely gráfban a csúcsok fokszámösszege kétszerese az élek számának. A duális formában a lemma kimondja, hogy síkgráfban a gráf tartományainak az oldalainak összege az élek kétszeresével egyezik meg.[27]

Síkgráf mediális gráfja izomorf duálisának mediális gráfjával. Két különböző síkgráf pontosan akkor rendelkezik izomorf mediális gráfokkal, ha egymás duálisai.[28]

Egy legalább négy csúccsal rendelkező síkbarajzolható gráf pontosan akkor maximális (nem adható újabb él a síkbarajzolhatóság megőrzésével), ha duálisa 3-összefüggő és 3-reguláris.[29]

Egy összefüggő síkgráf pontosan akkor tartalmaz Euler-utat (minden csúcsának fokszáma páros), ha duálisa páros gráf.[30] Egy síkgráf Hamilton-köre megfelel a duális gráf csúcsainak két részhalmazba (a kör külső és belső része) való particionálásával, ahol a felosztás mindkét részének feszített részgráfjai fák. A 3-reguláris, páros poliédergráfok Hamilton-körűségéről szóló Barnette-sejtés ekvivalens azzal a sejtéssel, hogy minden Euler-utat tartalmazó maximális síkgráf két feszített részfára particionálható.[31]

Ha egy G síkbarajzolható gráf Tutte-polinomja TG(x,y), akkor duálisának Tutte-polinomja előállítható az x és y felcserélésével. Ezért ha a Tutte-polinom valamely speciális értéke G valamely struktúrájáról szolgáltat információt, akkor az argumentumok cserélje után a duális struktúráiról fog információt szolgáltatni. Például az erős irányítások száma TG(0,2), míg a körmentes irányítások száma TG(2,0).[32] A hídmentes síkbarajzolható gráfok k színnel színezése megfelel a duális gráf sehol sem nulla folyamjainak modulo k. Például a négyszíntétel (ami kimondja minden síkgráf 4-színezésének létezését) úgy is kifejezhető, hogy minden hídmentes síkbarajzolható gráf duálisa rendelkezik sehol sem nulla 4-folyammal. A k-színezések számolhatók (valamely könnyen kiszámítható tényezőig) a TG(1 − k,0) Tutte-polinomértékkel, míg a duális sehol sem nulla k-folyamok a TG(0,1 − k) polinomértékkel.[33]

Egy st-síkgráf egy összefüggő síkgráf egy hozzátartozó bipoláris irányítással, mely körmentessé teszi egyetlen forrással és egyetlen nyelővel, melyek a lerajzolás ugyanazon tartományán helyezkednek el. Egy ilyen gráf erősen összefüggő gráffá tehető egyetlen él hozzáadásával a nyelőtől a forrásig, a külső tartományon keresztül. Ennek a kiegészített síkgráfnak a duálisa maga is egy st-síkgráf kiegészített változata.[34]

Variációk

szerkesztés

Irányított gráfok

szerkesztés

Egy irányított síkgráf duálisa is irányítottá tehető a duális éleknek az eredeti élekhez képest óramutató járása szerint 90°-kal való irányításával.[34] Ez a szó szoros értelmében nem az irányított síkgráf duálisa, mivel a G gráfból kiindulva és az előbb említett műveletet kétszer elvégezve nem az eredeti G gráfhoz jutunk vissza, hanem a G gráf transzponáltjához, azaz éleinek megfordításához. A műveletet négyszer elvégezve jutunk vissza az eredeti gráfhoz.

Gyenge duális

szerkesztés

Egy síkgráf gyenge duálisa a duális gráf részgráfja; az a gráf, melynek csúcsai a beágyazás egy korlátos tartományának felelnek meg, élei pedig a szomszédos korlátos tartományoknak megfelelő csúcsok között húzódnak. Egy síkgráf pontosan akkor külsíkgráf, ha gyenge duálisa erdő; egy síkgráf pontosan akkor Halin-gráf, ha gyenge duálisa kétszeresen összefüggő külsíkgráf.

Tekintsünk egy G síkgráfot, legyen G+ a következőképpen megkapott sík-multigráf: adjunk egy új v csúcsot G korlátlan tartományához, majd v-t kössük össze a külső tartomány minden csúcsával (akár többször, ha egy csúcs többször előfordul a külső tartomány határán); ekkor G a G+ duálisának gyenge duálisa.[35][36]

Végtelen gráfok és tesszalációk

szerkesztés

A dualitás fogalma értelmezhető a síkbarajzolható véges gráfok mellett a síkbarajzolható végtelen gráfokon is. Óvatosan el kell kerülni azonban az olyan topológiai komplikációkat, mint a sík olyan pontjai, melyet nem tartalmaznak sem a gráf élei vagy csúcsai, de nem része a gráftól diszjunkt nyílt tartománynak sem. Ha az összes tartomány olyan korlátos térrész, amit a gráf egy köre határol, a végtelen gráf síkba ágyazása úgy is tekinthető, mint a sík egy parkettázása, azaz a sík lefedése olyan zárt korongokkal (a tesszaláció csempéivel), melyek belsejei diszjunkt nyílt korongok. A sík-dualitásból levezethető egy új fogalom, a duális csempézés, amikor egy meglévő tesszaláció csempéinek közepébe egy-egy csúcsot helyezünk el, és a szomszédos csempékbe rajzolt csúcsokat összekötjük.[37]

 
Egy véges ponthalmazhoz (fekete pontok) tartozó Voronoj-diagram (piros) és Delaunay-háromszögelés (fekete)

A duális csempézés koncepciója alkalmazható a sík véges számú régióra való felbontásánál is. Közeli rokona a síkgráf-dualitásnak, de ebben az esetben attól némileg eltér. Például egy véges ponthalmaz Voronoj-diagramja a sík olyan sokszögekre felosztása, melyben lévő pontok közelebb vannak az adott sokszög generátorpontjához, mint a többiéhez. A bemenet konvex burkán lévő generátorpontok hozzák létre a korlátlan Voronoj-cellákat, melyek közül kettőnek oldalai véges egyenesszakaszok helyett végtelen félegyenesek. A Voronoj-diagram duálisa a bemenet Delaunay-háromszögelése, egy síkgráf, amiben két generátorpontot akkor köt össze él, ha létezik a két pontot összekötő, más pontot nem érintő kör. A bemenet konvex burkának élei a Delaunay-háromszögelésben is szereplő élek, de ezek félegyenesek, nem a Voronoj-diagram egyenes szakaszai. A Voronoj-diagram és a Delaunay-háromszögelés közötti dualitás kétféleképpen alakítható át véges gráfok közötti dualitásba: hozzáadhatunk egy a végtelenben lévő mesterséges csúcsot a Voronoj-diagramhoz, hogy az összes félegyenes végpontjául szolgáljon,[38] vagy kezelhetjük a Voronoj-diagram korlátos részét a Delaunay-háromszögelés gyenge duálisaként. Bár a Voronoj-diagram és a Delaunay-háromszögelés duálisak, síkbarajzolásukban a duális élpárokon kívül más élmetszések is előfordulhatnak. A Delaunay-háromszög minden csúcsa a Voronoj-diagram megfelelő tartományában helyezkedik el. A Voronoj-diagram minden csúcsa pedig a Delaunay-háromszögelés megfelelő háromszöge köréírt körének középpontjában, de ez a pont a háromszögön kívülre is eshet.

Nem síkfelületbe történő beágyazások

szerkesztés
 
A K7 a Heawood-gráf duálisa a tóruszon

A dualitás fogalma kiterjeszthető a síkon kívül más, kétdimenziós sokaságokba történő beágyazásokra is. A definíció ugyanaz: a sokaságba ágyazott gráf komplementerének minden összefüggő komponenséhez egy duális csúcs tartozik, és egy duális él minden olyan eredeti gráfélhez, ami a duális csúcsok eredetijei között húzódott. Az elgondolás legtöbbször korlátozódik az olyan beágyazásokra, ahol minden tartomány egy topologikus korong; ez annak a síkbeli követelménynek az általánosítása, hogy a gráf összefüggő legyen. Ezzel a korlátozással élve, bármely felületbe beágyazott gráf duálisa rendelkezik ugyanazon felületre való természetes beágyazással úgy, hogy a duális duálisa izomorf az eredeti gráffal és izomorfan beágyazott az eredeti gráfba. Például a K7 teljes gráf tóruszra rajzolható: nem síkbarajzolható, de beágyazható a tóruszfelületbe úgy, hogy a beágyazás minden tartománya háromszög. Ennek a beágyazásnak a Heawood-gráf a duálisa.[39]

Ugyanaz az elgondolás kiválóan működik nem irányítható felületek esetében is. Például a K6 beágyazható a projektív síkba tíz háromszögű tartománnyal félikozaéderként, duálisa pedig a Petersen-gráf, beágyazva mint féldodekaéder.[40]

Bármely síkbarajzolható gráf beágyazható más felületekbe is, és az ilyen beágyazásainak duálisai különbözőek lehetnek a síkbarajzolás duálisaitól. Például a kocka négy Petrie-sokszöge (a kocka két szemközti csúcsának eltávolításával kapott hatszögek) a kocka tóruszba ágyazásának hatszögű tartományait adják. Ennek a beágyazásnak a duálisa négy csúccsal rendelkezik, tulajdonképpen a K4 teljes gráf kettőzött élekkel. Ennek a duális gráfnak a tóruszba ágyazásakor minden csúcsból hat él indul ki, a csúcs körül kétszer körbeérnek a három másik csúcs irányába. A síkbeli helyzettől eltérően a kocka és duálisának tóruszba ágyazása nem egyedi; a kockagráfnak számos más tóruszba ágyazása létezik, különböző duálisokkal.[39]

Az eredeti és a duális gráf között a síkbarajzoláskor működő ekvivalenciák sok esetben nem általánosíthatók a többi felületbe ágyazásra, vagy külön odafigyelést igényelnek az általánosítás elvégzésekor.

Matroidok és algebrai duálisok

szerkesztés

Egy összefüggő G gráf algebrai duálisa olyan G★ gráf, melyre igaz, hogy G és G★ élhalmaza megegyezik, G bármely köre G★ egy vágása és G bármely vágása G★ egy köre. Minden síkbarajzolható gráfnak van algebrai duálisa, ami általában nem egyedi (bármely, síkbarajzolás által definiált duális megfelel). Az állítás megfordítása is igaz, ahogy azt Hassler Whitney megállapította a Whitney-féle síkgráfkritériumban:[41]

Egy G összefüggő gráf pontosan akkor síkbarajzolható, ha létezik algebrai duálisa.

Ugyanez a tény kifejezhető a matroidok elméletének felhasználásával is. Ha M a G gráf grafikus matroidja, akkor a G★ gráf pontosan akkor a G algebrai duálisa, ha G★ grafikus matroidja éppen az M duális matroidja. Ekkor Whitney síkgráfkritériuma átfogalmazható úgy, hogy az M grafikus matroid duális matroidja pontosan akkor maga is grafikus matroid, ha az M alapjául szolgáló G gráf síkbarajzolható. Ha G síkbarajzolható, a duális matroid a G duálisának grafikus matroidja. További következmény, hogy G összes síkbarajzolásához tartozó duálisoknak izomorfak a grafikus matroidjaik.[42]

A nem síkfelületekbe történő beágyazáskor a síkduálistól eltérően a duális gráf általában nem az eredeti gráf algebrai duálisa. Továbbá nem síkbarajzolható G gráf duális matroidja maga nem grafikus matroid. Mindazonáltal egy olyan matroid, melynek körei megfelelnek G vágásainak, és ebben az értelemben tekinthető a G általánosított algebrai duálisának.[43]

Az Euler-utat tartalmazó és a páros síkbarajzolható gráfok közötti dualitás kiterjeszthető a bináris matroidokra (melyek magukban foglalják a síkbarajzolható gráfok grafikus matroidjait): egy bináris matroid pontosan akkor Euler-féle, ha duális matroidja páros.[30] A girthparaméter és élösszefüggőség duális fogalmait a matroidelmélet a matroid girthparaméterében (bőségében) egyesíti: síkbarajzolható gráf grafikus matroidjának bősége megegyezik a gráf bőségével, a duális matroid (a duális gráf grafikus matroidjának) bősége pedig a gráf élösszefüggőségével.[18]

Alkalmazásai

szerkesztés

Gráfelméleti alkalmazásai mellett a síkbarajzolható gráfok dualitását számos más matematikai és számítási területen felhasználják.

A földrajzi információs rendszerekben a lefolyási hálózatok (a víz patakok, folyók stb. rendszereiben történő lefolyását leíró hálózat) a vízválasztók sejtes rendszerű hálózatainak duálisát képezik. Ez a dualitás megmagyarázható a lefolyási hálózat megfelelő skálán, rácsgráf feszítőfájaként való modellezésével, ahol a vízválasztók a duális rácsgráf gerincvonalainak komplementer feszítőfájaként jelennek meg.[44]

A számítógépes látás területén a digitális képeket apró, négyzetes pixelekre osztják föl, melyek mindegyike saját színnel rendelkezik. Ennek a pixelekre való felosztásnak a duális gráfjában minden pixelhez egy csúcs tartozik, él pedig az azonos élen fekvő pixelpárok között; ez a hasonló színű összefüggő területek klaszterezésében hasznos.[45]

A számítási geometria területén a Voronoj-diagramok és Delaunay-háromszögelések közti dualitásból az is következik, hogy bármely, Voronoj-diagramot létrehozó algoritmus azonnal konvertálható egy olyanná, ami Delaunay-háromszögelést állít elő, és megfordítva.[46] Ugyanez a dualitás felhasználható a végeselemes hálógenerálásra is. A Voronoj-diagramokon alapuló, ponthalmazok a felületen egyenletesebb távolságeloszlású helyzetbe mozgatására szolgáló Lloyd-algoritmust gyakran használják a duális Delaunay-háromszögelés által leírt végeselemes hálók kisimítására. A módszer javítja a háló minőségét azzal, hogy a háromszögeket egyenletesebb méretre és alakra hozza.[47]

A CMOS áramkörök logikai szintézise során a szintetizálandó függvény Boole-algebrai kifejezés formájában szerepel. Később ezt a kifejezést átalakítják két soros-párhuzamos multigráffá. Ezek a gráfok kapcsolási rajzként értelmezhetők, melyben a gráfok élei tranzisztorokat jelképeznek, melyeket a függvény bemenetei kapuznak. Az egyik áramkör a függvényt számítja ki, a másik a függvény komplementerét. A két áramkör egyike megkapható a kifejezés logikai vagy és logikai és műveleteinek soros-párhuzamos gráfkompozíciójával. A másik áramkör ennek a konstrukciónak fordítottjával, a kifejezés műveleteinek párhuzamos-soros gráfkompozíciójával állítható elő.[48] Ez a két áramkör, kiegészítve őket egy-egy, a bemenetet a kimenettel összekötő éllel, duális gráfok a síkbarajzolás duálisának értelmében.[49]

Története

szerkesztés

A konvex testek dualitásáról elsőként Johannes Kepler 1619-es könyvéből, a Harmonices Mundi-ból („A világ harmóniájáról”) értesülhetünk.[50] A poliéderek kontextusán kívül a síkgráfok duálisai már 1725-ben felmerülnek Pierre Varignon posztumusz megjelent munkájában, a Nouvelle Méchanique ou Statique-ban. Ezzel megelőzte Leonhard Euler 1736-os, a königsbergi hidak problémáját taglaló művét, amire pedig gyakran a gráfelmélet legelső műveként hivatkoznak. Varignon úgy vizsgálta a merevítő szerkezeti elemek statikus rendszereiben fellépő erőket, hogy a merevítések duális gráfját rajzolta meg, melynek élhosszai a merevítő elemekre ható erőkkel arányosak; az ilyen duális gráfot a Cremona-diagramok közé sorolják.[51] A négyszínsejtéssel összefüggésben térképek (a sík régiókra való osztásának) duális gráfjai már 1879-ben megjelennek Alfred Kempe-nél, amit nem síkfelületek térképeire Lothar Heffter terjeszt ki 1891-ben.[52] A dualitás, mint absztrakt síkgráfokon értelmezett művelet 1931-ben Hassler Whitney-nél jelenik meg.[53]

Jegyzetek

szerkesztés
  1. ↑ VIK Wiki
  2. ↑ Katona Gyula Y – Recski András – Szabó Csaba: A számítástudomány alapjai. 2002–01–01. ISBN 9789639326248 Hozzáférés: 2015. december 20.  
  3. ↑ van Lint, J. H. & Wilson, Richard Michael (1992), A Course in Combinatorics, Cambridge University Press, p. 411, ISBN 0-521-42260-4.
  4. ↑ Weisstein, Eric W.: Self-dual graph (angol nyelven). Wolfram MathWorld
  5. ↑ a b Servatius, Brigitte & Christopher, Peter R. (1992), "Construction of self-dual graphs", The American Mathematical Monthly 99 (2): 153–158, DOI 10.2307/2324184.
  6. ↑ Thulasiraman, K. & Swamy, M. N. S. (2011), Graphs: Theory and Algorithms, John Wiley & Sons, Exercise 7.11, p. 198, ISBN 978-1-118-03025-7, <https://books.google.com/books?id=rFH7eQffQNkC&pg=PA198>.
  7. ↑ See the proof of Theorem 5 in (Servatius & Christopher 1992).
  8. ↑ Nishizeki, Takao & Chiba, Norishige (2008), Planar Graphs: Theory and Algorithms, Dover Books on Mathematics, Dover Publications, p. 16, ISBN 978-0-486-46671-2, <https://books.google.com/books?id=1Nl4BpacvpwC&pg=PA16>.
  9. ↑ Jensen, Tommy R. & Toft, Bjarne (1995), Graph Coloring Problems, vol. 39, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, p. 17, ISBN 978-0-471-02865-9.
  10. ↑ Balakrishnan, V. K. (1997), Schaum's Outline of Graph Theory, McGraw Hill Professional, Problem 8.64, p. 229, ISBN 978-0-07-005489-9.
  11. ↑ a b Foulds, L. R. (2012), Graph Theory Applications, Springer, pp. 66–67, ISBN 978-1-4612-0933-1, <https://books.google.com/books?id=5G4QBwAAQBAJ&pg=PA66>.
  12. ↑ Bondy, Adrian & Murty, U.S.R. (2008), "Planar Graphs", Graph Theory, vol. 244, Graduate Texts in Mathematics, Springer, Theorem 10.28, p. 267, ISBN 978-1-84628-969-9, doi:10.1007/978-1-84628-970-5, <https://books.google.com/books?id=HuDFMwZOwcsC&lpg=PA267>
  13. ↑ Angelini, Patrizio; Bläsius, Thomas & Rutter, Ignaz (2014), "Testing mutual duality of planar graphs", International Journal of Computational Geometry and Applications 24 (4): 325–346, DOI 10.1142/S0218195914600103.
  14. ↑ Diestel, Reinhard (2006), Graph Theory, vol. 173, Graduate Texts in Mathematics, Springer, p. 25, ISBN 978-3-540-26183-4, <https://books.google.com/books?id=aR2TMYQr2CMC&pg=PA25>.
  15. ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.
  16. ↑ Godsil, Chris & Royle, Gordon F. (2013), Algebraic Graph Theory, vol. 207, Graduate Texts in Mathematics, Springer, Theorem 14.3.1, p. 312, ISBN 978-1-4613-0163-9, <https://books.google.com/books?id=GeSPBAAAQBAJ&pg=PA312>.
  17. ↑ Oxley, J. G. (2006), Matroid Theory, vol. 3, Oxford Graduate Texts in Mathematics, Oxford University Press, p. 93, ISBN 978-0-19-920250-8, <https://books.google.com/books?id=puKta1Hdz-8C&pg=PA93>.
  18. ↑ a b Cho, Jung Jin; Chen, Yong & Ding, Yu (2007), "On the (co)girth of a connected matroid", Discrete Applied Mathematics 155 (18): 2456–2470, DOI 10.1016/j.dam.2007.06.015.
  19. ↑ a b Hartvigsen, D. & Mardon, R. (1994), "The all-pairs min cut problem and the minimum cycle basis problem on planar graphs", SIAM Journal on Discrete Mathematics 7 (3): 403–418, DOI 10.1137/S0895480190177042.
  20. ↑ Noy, Marc (2001), "Acyclic and totally cyclic orientations in planar graphs", American Mathematical Monthly 108 (1): 66–68, DOI 10.2307/2695680.
  21. ↑ Tutte, W. T. (1984), Graph theory, vol. 21, Encyclopedia of Mathematics and its Applications, Reading, MA: Addison-Wesley Publishing Company, Advanced Book Program, p. 289, ISBN 0-201-13520-5.
  22. ↑ Riley, T. R. & Thurston, W. P. (2006), "The absence of efficient dual pairs of spanning trees in planar graphs", Electronic Journal of Combinatorics 13 (1): Note 13, 7, <http://www.combinatorics.org/Volume_13/Abstracts/v13i1n13.html>.
  23. ↑ Lyons, Russell (1998), "A bird's-eye view of uniform spanning trees and forests", Microsurveys in discrete probability (Princeton, NJ, 1997), vol. 41, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Amer. Math. Soc., Providence, RI, pp. 135–162. See in particular pp. 138–139.
  24. ↑ Flammini, Alessandro (October 1996), Scaling Behavior for Models of River Network, Ph.D. thesis, International School for Advanced Studies, pp. 40–41, <http://hdl.handle.net/1963/5601>.
  25. ↑ Sommerville, D. M. Y. (1958), An Introduction to the Geometry of N Dimensions, Dover.
  26. ↑ Eppstein, David (2003), "Dynamic generators of topologically embedded graphs", Proceedings of the 14th ACM/SIAM Symposium on Discrete Algorithms, pp. 599–608.
  27. ↑ Harary, Frank (1969), Graph Theory, Reading, Mass.: Addison-Wesley Publishing Co., Theorem 9.4, p. 142.
  28. ↑ Gross, Jonathan L. & Yellen, Jay, eds. (2003), Handbook of Graph Theory, CRC Press, p. 724, ISBN 978-1-58488-090-5, <https://books.google.com/books?id=mKkIGIea_BkC&lpg=PA724>.
  29. ↑ He, Xin (1999), "On floor-plan of plane graphs", SIAM Journal on Computing 28 (6): 2150–2167, DOI 10.1137/s0097539796308874.
  30. ↑ a b Welsh, D. J. A. (1969), "Euler and bipartite matroids", Journal of Combinatorial Theory 6: 375–377, DOI 10.1016/s0021-9800(69)80033-5.
  31. ↑ Florek, Jan (2010), "On Barnette's conjecture", Discrete Mathematics 310 (10–11): 1531–1535, DOI 10.1016/j.disc.2010.01.018.
  32. ↑ Las Vergnas, Michel (1980), "Convexity in oriented matroids", Journal of Combinatorial Theory, Series B 29 (2): 231–243, DOI 10.1016/0095-8956(80)90082-9.
  33. ↑ Tutte, William Thomas (1953). „A contribution to the theory of chromatic polynomials”. 
  34. ↑ a b di Battista, Giuseppe; Eades, Peter & Tamassia, Roberto et al. (1999), Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, p. 91, ISBN 978-0-13-301615-4.
  35. ↑ Fleischner, Herbert J.; Geller, D. P. & Harary, Frank (1974), "Outerplanar graphs and weak duals", Journal of the Indian Mathematical Society 38: 215–219.
  36. ↑ Sysło, Maciej M. & Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, vol. 1018, Lecture Notes in Mathematics, Springer-Verlag, pp. 248–256, DOI 10.1007/BFb0071635.
  37. ↑ Weisstein, Eric W.: Dual Tessellation (angol nyelven). Wolfram MathWorld
  38. ↑ Samet, Hanan (2006), Foundations of Multidimensional and Metric Data Structures, Morgan Kaufmann, p. 348, ISBN 978-0-12-369446-1, <https://books.google.com/books?id=vO-NRRKHG84C&pg=PA348>.
  39. ↑ a b Gagarin, Andrei; Kocay, William & Neilson, Daniel (2003), "Embeddings of small graphs on the torus", Cubo 5: 351–371, <http://www.cs.rhul.ac.uk/home/agagarin/Embeddings.pdf>. Hozzáférés ideje: 2017-04-17.
  40. ↑ Nakamoto, Atsuhiro & Negami, Seiya (2000), "Full-symmetric embeddings of graphs on closed surfaces", Memoirs of Osaka Kyoiku University 49 (1): 1–15.
  41. ↑ Whitney, Hassler (1932), "Non-separable and planar graphs", Transactions of the American Mathematical Society 34 (2): 339–362, DOI 10.1090/S0002-9947-1932-1501641-2.
  42. ↑ Oxley, J. G. (2006), "5.2 Duality in graphic matroids", Matroid Theory, vol. 3, Oxford graduate texts in mathematics, Oxford University Press, p. 143, ISBN 978-0-19-920250-8.
  43. ↑ Tutte, W. T. (2012), Graph Theory As I Have Known It, vol. 11, Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press, p. 87, ISBN 978-0-19-966055-1, <https://books.google.com/books?id=uYW2tttqQ74C&pg=PA87>.
  44. ↑ Chorley, Richard J. & Haggett, Peter (2013), Integrated Models in Geography, Routledge, p. 646, ISBN 978-1-135-12184-6, <https://books.google.com/books?id=8c79AQAAQBAJ&pg=PA646>.
  45. ↑ Kandel, Abraham; Bunke, Horst & Last, Mark (2007), Applied Graph Theory in Computer Vision and Pattern Recognition, vol. 52, Studies in Computational Intelligence, Springer, p. 16, ISBN 978-3-540-68020-8, <https://books.google.com/books?id=C8tuCQAAQBAJ&pg=PA16>.
  46. ↑ Devadoss, Satyan L. & O'Rourke, Joseph (2011), Discrete and Computational Geometry, Princeton University Press, p. 111, ISBN 978-1-4008-3898-1, <https://books.google.com/books?id=InJL6iAaIQQC&pg=PA111>.
  47. ↑ Du, Qiang & Gunzburger, Max (2002), "Grid generation and optimization based on centroidal Voronoi tessellations", Applied Mathematics and Computation 133 (2–3): 591–607, DOI 10.1016/S0096-3003(01)00260-0.
  48. ↑ Piguet, Christian (2004), "7.2.1 Static CMOS Logic", Low-Power Electronics Design, CRC Press, pp. 7-1–7-2, ISBN 978-1-4200-3955-9, <https://books.google.com/books?id=QzKfa_Y4IuIC&pg=SA7-PA1>.
  49. ↑ Kaeslin, Hubert (2008), "8.1.4 Composite or complex gates", Digital Integrated Circuit Design: From VLSI Architectures to CMOS Fabrication, Cambridge University Press, p. 399, ISBN 978-0-521-88267-5, <https://books.google.com/books?id=gdRStcYgf2oC&pg=PA399>.
  50. ↑ Richeson, David S. (2012), Euler's Gem: The Polyhedron Formula and the Birth of Topology, Princeton University Press, pp. 58–61, ISBN 978-1-4008-3856-1, <https://books.google.com/books?id=KUYLhOVkaV4C&pg=PA58>.
  51. ↑ Rippmann, Matthias (2016), Funicular Shell Design: Geometric Approaches to Form Finding and Fabrication of Discrete Funicular Structures, Habilitation thesis, Diss. ETH No. 23307, ETH Zurich, pp. 39–40, DOI 10.3929/ethz-a-010656780. Lásd még Erickson, Jeff (June 9, 2016), Reciprocal force diagrams from Nouvelle Méchanique ou Statique by Pierre de Varignon (1725), <https://plus.google.com/+JeffErickson/posts/6UyRPX7ShXV>.
  52. ↑ Biggs, Norman; Lloyd, E. Keith & Wilson, Robin J. (1998), Graph Theory, 1736–1936, Oxford University Press, p. 118, ISBN 978-0-19-853916-2, <https://books.google.com/books?id=XqYTk0sXmpoC&pg=PA118>.
  53. ↑ Whitney, Hassler (1931), "A theorem on graphs", Annals of Mathematics, Second Series 32 (2): 378–390, DOI 10.2307/1968197.

További információk

szerkesztés

Fordítás

szerkesztés

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

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Duális_gráf&oldid=25467812”