right|thumb|upright=1.3|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 síkgráf duális gráfja az a gráf (multigráf), mely a következő módon állítható elő. csúcsai az eredeti síkgráf tartományai; ha két -beli tartományt egy él választ el egymástól, -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 -beli élnek létezik -beli, duális megfelelője, melynek végpontjai az két oldalán lévő tartományoknak megfelelő duális csúcsok. A duális gráf meghatározása függ 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ó.VIK Wiki
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 gráf az összefüggő gráf duálisa, akkor gráf is duálisa a 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. 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
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 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ó duális élből álló multigráf. Az ilyen gráfot dipólusgráfnak nevezzük. Megfordítva, az -élű dipólusgráf duálisa a körgráf..
Önduális gráfok
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. Léteznek azonban önduális, azonban nem poliéderből származó gráfok, mint amilyen az ábrán is látható. 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..
Az Euler-formulából adódóan minden csúcsú önduális gráfnak pontosan éle van.. 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.See the proof of Theorem 5 in .
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,. ezek a párosítások mindig kétirányúak: ha a síkgráf fogalma a duálisban fogalomnak felel meg, akkor a síkgráf fogalma éppen a duális 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 síkbarajzolható gráfban található elválasztó élek (hidak) egy az egyben megfeleltethetők duálisának hurokéleivel.. 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.. 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
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.. 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. 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 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..
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.. 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.Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) . Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. .
Ha síkbarajzolható összefüggő gráf, akkor minden egyszerű köre megfelel duálisában egy minimális vágási élhalmaznak, és viszont.. Ez a Jordan-féle görbetétel egy változatának is tekinthető: minden egyszerű kör szétválasztja 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.. 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).
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. 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. 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..
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)..
Feszítőfák