![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/b/ba/Duals_graphs.svg/langhu-640px-Duals_graphs.svg.png&w=640&q=50)
Duális gráf
speciális gráf / From Wikipedia, the free encyclopedia
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]
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/b/ba/Duals_graphs.svg/290px-Duals_graphs.svg.png)
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.