| dbo:abstract
|
- 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ó. Történelmileg a gráfok dualitását elsőként a szabályos testek közötti 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 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 „” 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 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 , , a és az integrált áramkörök tervezésének területein. (hu)
- 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ó. Történelmileg a gráfok dualitását elsőként a szabályos testek közötti 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 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 „” 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 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 , , a és az integrált áramkörök tervezésének területein. (hu)
|
