Duális gráf

Innen: testwiki
A lap korábbi változatát látod, amilyen imported>Porribot 2022. november 10., 14:32-kor történt szerkesztése után volt. (→További jellemzők: link korr. AWB)
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)
Ugrás a navigációhoz Ugrás a kereséshez
A piros gráf a kék gráf duálisa, és viszont.

A matematika, azon belül a gráfelmélet területén a Sablon:Mvar síkgráf duális gráfja az a Sablon:Mvar gráf (multigráf), mely a következő módon állítható elő. Sablon:Mvar csúcsai az eredeti Sablon:Mvar síkgráf tartományai; ha két Sablon:Mvar-beli tartományt egy él választ el egymástól, Sablon:Mvar-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 Sablon:Mvar-beli Sablon:Mvar élnek létezik Sablon:Mvar-beli, duális megfelelője, melynek végpontjai az Sablon:Mvar két oldalán lévő tartományoknak megfelelő duális csúcsok. A duális gráf meghatározása függ Sablon:Mvar 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]

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 Sablon:Mvar gráf az összefüggő Sablon:Mvar gráf duálisa, akkor Sablon:Mvar gráf is duálisa a Sablon:Mvar 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

Körök és dipólusok

Sablon:Több kép 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 Cn kör esetén a két régiót Sablon:Mvar különböző él választja el egymástól, a Cn duálisa egy két csúcsból (a tartományok duálisaiból) és a köztük húzódó Sablon:Mvar duális élből álló multigráf. Az ilyen gráfot dipólusgráfnak nevezzük. Megfordítva, az Sablon:Mvar-élű dipólusgráf duálisa a Cn körgráf.[3]

Önduális gráfok

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ó. Sablon:Harvtxt 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 Sablon:Mvar csúcsú önduális gráfnak pontosan Sablon:Math é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

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 Sablon:Mvar fogalma a duálisban Sablon:Mvar fogalomnak felel meg, akkor a síkgráf Sablon:Mvar fogalma éppen a duális Sablon:Mvar fogalmának felel meg.

Egyszerű gráfok / multigráfok

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 Sablon:Mvar síkbarajzolható gráfban található elválasztó élek (hidak) egy az egyben megfeleltethetők Sablon:Mvar 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

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 Sablon:Math 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

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 Sablon:Mvar síkbarajzolható összefüggő gráf, akkor Sablon:Mvar minden egyszerű köre megfelel Sablon:Mvar 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 Sablon:Mvar 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

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 Sablon:Mvar síkbarajzolható gráf Sablon:Mvar élhalmaza körmentes, akkor az Sablon:Mvar 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 Sablon:Mvar összefüggő, akkor az Sablon:Mvar komplementere duálisának élei körmentes részgráfot alkotnak. Az előzőek szerint, ha Sablon:Mvar mindkét tulajdonsággal rendelkezik – összefüggő és körmentes – ugyanez igaz a duális gráf komplementerére. Tehát Sablon:Mvar 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á, Sablon:Mvar 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 Sablon:Math, ahol Sablon:Mvar a csúcsok, Sablon:Mvar az élek, Sablon:Mvar pedig a tartományok száma. Bármely feszítőfa és komplementer duális feszítőfája az éleket két, Sablon:Math, illetve Sablon:Math részhalmazra particionálja, a két részhalmaz méretét az egyenlőséghez adva

Sablon:Math

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

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 Sablon:Mvar síkbarajzolható gráf Tutte-polinomja Sablon:Math, akkor duálisának Tutte-polinomja előállítható az Sablon:Mvar és Sablon:Mvar felcserélésével. Ezért ha a Tutte-polinom valamely speciális értéke Sablon:Mvar 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 Sablon:Math, míg a körmentes irányítások száma Sablon:Math.[32] A hídmentes síkbarajzolható gráfok Sablon:Mvar színnel színezése megfelel a duális gráf sehol sem nulla folyamjainak modulo Sablon:Mvar. 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 Sablon:Mvar-színezések számolhatók (valamely könnyen kiszámítható tényezőig) a Sablon:Math Tutte-polinomértékkel, míg a duális sehol sem nulla Sablon:Mvar-folyamok a Sablon:Math 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

Irányított gráfok

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 Sablon:Mvar gráfból kiindulva és az előbb említett műveletet kétszer elvégezve nem az eredeti Sablon:Mvar gráfhoz jutunk vissza, hanem a Sablon:Mvar 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

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 Sablon:Mvar síkgráfot, legyen Sablon:Math a következőképpen megkapott sík-multigráf: adjunk egy új Sablon:Mvar csúcsot Sablon:Mvar korlátlan tartományához, majd Sablon:Mvar-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 Sablon:Mvar a Sablon:Math duálisának gyenge duálisa.[35][36]

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

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

Sablon:Több kép 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 Sablon:Math 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 Sablon:Math 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 Sablon:Math 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

Egy összefüggő Sablon:Mvar gráf algebrai duálisa olyan Sablon:Math gráf, melyre igaz, hogy Sablon:Mvar és Sablon:Math élhalmaza megegyezik, Sablon:Mvar bármely köre Sablon:Math egy vágása és Sablon:Mvar bármely vágása Sablon:Math 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 Sablon:Mvar ö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 Sablon:Mvar a Sablon:Mvar gráf grafikus matroidja, akkor a Sablon:Math gráf pontosan akkor a Sablon:Mvar algebrai duálisa, ha Sablon:Math grafikus matroidja éppen az Sablon:Mvar duális matroidja. Ekkor Whitney síkgráfkritériuma átfogalmazható úgy, hogy az Sablon:Mvar grafikus matroid duális matroidja pontosan akkor maga is grafikus matroid, ha az Sablon:Mvar alapjául szolgáló Sablon:Mvar gráf síkbarajzolható. Ha Sablon:Mvar síkbarajzolható, a duális matroid a Sablon:Mvar duálisának grafikus matroidja. További következmény, hogy Sablon:Mvar ö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ó Sablon:Mvar gráf duális matroidja maga nem grafikus matroid. Mindazonáltal egy olyan matroid, melynek körei megfelelnek Sablon:Mvar vágásainak, és ebben az értelemben tekinthető a Sablon:Mvar á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

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

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

Sablon:Reflist

További információk

Fordítás

Sablon:Fordítás

Sablon:Portál

  1. ↑ VIK Wiki
  2. ↑ Sablon:CitLib
  3. ↑ Sablon:Citation.
  4. ↑ Sablon:Mathworld
  5. ↑ 5,0 5,1 Sablon:Citation.
  6. ↑ Sablon:Citation.
  7. ↑ See the proof of Theorem 5 in Sablon:Harvtxt.
  8. ↑ Sablon:Citation.
  9. ↑ Sablon:Citation.
  10. ↑ Sablon:Citation.
  11. ↑ 11,0 11,1 Sablon:Citation.
  12. ↑ Sablon:Citation
  13. ↑ Sablon:Citation.
  14. ↑ Sablon:Citation.
  15. ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. Sablon:ISBN.
  16. ↑ Sablon:Citation.
  17. ↑ Sablon:Citation.
  18. ↑ 18,0 18,1 Sablon:Citation.
  19. ↑ 19,0 19,1 Sablon:Citation.
  20. ↑ Sablon:Citation.
  21. ↑ Sablon:Citation.
  22. ↑ Sablon:Citation.
  23. ↑ Sablon:Citation. See in particular pp. 138–139.
  24. ↑ Sablon:Citation.
  25. ↑ Sablon:Citation.
  26. ↑ Sablon:Citation.
  27. ↑ Sablon:Citation.
  28. ↑ Sablon:Citation.
  29. ↑ Sablon:Citation.
  30. ↑ 30,0 30,1 Sablon:Citation.
  31. ↑ Sablon:Citation.
  32. ↑ Sablon:Citation.
  33. ↑ Sablon:Cite journal
  34. ↑ 34,0 34,1 Sablon:Citation.
  35. ↑ Sablon:Citation.
  36. ↑ Sablon:Citation.
  37. ↑ Sablon:Mathworld
  38. ↑ Sablon:Citation.
  39. ↑ 39,0 39,1 Sablon:Citation.
  40. ↑ Sablon:Citation.
  41. ↑ Sablon:Citation.
  42. ↑ Sablon:Citation.
  43. ↑ Sablon:Citation.
  44. ↑ Sablon:Citation.
  45. ↑ Sablon:Citation.
  46. ↑ Sablon:Citation.
  47. ↑ Sablon:Citation.
  48. ↑ Sablon:Citation.
  49. ↑ Sablon:Citation.
  50. ↑ Sablon:Citation.
  51. ↑ Sablon:Citation. Lásd még Sablon:Citation.
  52. ↑ Sablon:Citation.
  53. ↑ Sablon:Citation.
A lap eredeti címe: „https://hu.wiki.beta.math.wmflabs.org/w/index.php?title=Duális_gráf&oldid=3404”