Duális gráf forrásának megtekintése

[[Fájl:Duals_graphs.svg|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 {{mvar|G}} [[síkbarajzolható gráf|síkgráf]] '''duális gráf'''ja az a {{mvar|G*}} [[gráf]] ([[multigráf]]), mely a következő módon állítható elő. {{mvar|G*}} csúcsai az eredeti {{mvar|G}} síkgráf tartományai; ha két {{mvar|G}}-beli tartományt egy él választ el egymástól, {{mvar|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 {{mvar|G}}-beli {{mvar|e}} élnek létezik {{mvar|G*}}-beli, duális megfelelője, melynek végpontjai az {{mvar|e}} két oldalán lévő tartományoknak megfelelő duális csúcsok. A duális gráf meghatározása függ {{mvar|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 ([[gráfizomorfizmus|izomorfia]] erejéig), egy gráfnak létezhetnek különböző (nem izomorf) duálisai, melyek különböző (nem [[Homeomorfia|homeomorf]]) beágyazásaiból származnak. Síkgráf duálisa is síkbarajzolható.<ref>[https://wiki.sch.bme.hu/A_sz%C3%A1m%C3%ADt%C3%A1studom%C3%A1ny_alapjai_-_Seg%C3%A9danyagok_a_vizsg%C3%A1hoz#Defin.C3.ADci.C3.B3k_11 VIK Wiki]</ref>

Történelmileg a gráfok dualitását elsőként a [[szabályos test]]ek közötti [[duális poliéder|dualitási]] viszonyaiban ismerték fel. A gráfok dualitása a duális poliéderek és tesszellációk [[topológia|topologikus]] általánosítása, melyek további, algebrai általánosítása a [[matroid duálisa|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áf]]ok 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áf]]oknak neveznek.

Azért használjuk a „[[dualitás (matematika)|duális]]” kifejezést, mert a dualitási tulajdonság [[Szimmetria|szimmetrikus]], azaz ha {{mvar|H}} gráf az [[összefüggőség (gráfelmélet)|összefüggő]] {{mvar|G}} gráf duálisa, akkor {{mvar|G}} gráf is duálisa a {{mvar|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ás (gráfelmélet)|vágások]] felelnek meg az eredeti gráf [[Kör (gráfelmélet)|köreinek]] és fordítva. A [[feszítőfa|feszítőfák]] duálisai a feszítőfák [[Komplementer gráf|komplementereivel]] egyeznek meg.<ref>{{CitLib|tit = A számítástudomány alapjai|url = https://books.google.hu/books/about/A_Sz%25C3%25A1m%25C3%25ADt%25C3%25A1studom%25C3%25A1ny_Alapjai.html?id=O-af3kHW4SoC|ann = 2002-01-01|isbn = 9789639326248|aut = Katona Gyula Y|aut2 = Recski András|aut3 = Szabó Csaba|accd = 2015-12-20}}</ref> Az egyszerű gráfok (párhuzamos és hurokélek nélküli gráfok) duálisai pedig a [[k-szorosan élösszefüggő gráf|3-szorosan élösszefüggő gráfok]]

A duális gráfok segítenek megérteni az [[útvesztő]]k és [[vízgyűjtő terület]]ek 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===
{{Több kép|kép1=Dipole graph.svg|szöveg1=[[Dipólusgráf]]|szélesség1=200|kép2=Intercpunetring.png|szöveg2= [[Körgráf]]|szélesség2=158}}
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 <math>C_n</math> kör esetén a két régiót {{mvar|n}} különböző él választja el egymástól, a <math>C_n</math> duálisa egy két csúcsból (a tartományok duálisaiból) és a köztük húzódó {{mvar|n}} duális élből álló [[multigráf]]. Az ilyen gráfot [[dipólusgráf]]nak nevezzük. Megfordítva, az {{mvar|n}}-élű dipólusgráf duálisa a <math>C_n</math> körgráf.<ref>{{citation|title=A Course in Combinatorics|first1=J. H.|last1=van Lint|author1-link=J. H. van Lint|first2=Richard Michael|last2=Wilson|author2-link=R. M. Wilson|publisher=Cambridge University Press|year=1992|page=411|isbn=0-521-42260-4}}.</ref>

===Önduális gráfok===
[[File:Self-dual graph.svg|thumb|upright=0.75|Egy önduális gráf]]
Egy síkgráf akkor '''önduális''', ha saját duálisával [[gráfizomorfizmus|izomorf]]. Az [[önduális poliéder]]ekből (konkrétan [[gúla|gúlákból]]) származtatható [[kerékgráf]]ok önduális gráfok végtelen családját alkotják.<ref>{{mathworld | urlname = Self-DualGraph | title = Self-dual graph}}</ref><ref name="sc92"/> Léteznek azonban önduális, azonban nem poliéderből származó gráfok, mint amilyen az ábrán is látható. {{harvtxt|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.<ref name="sc92">{{citation
 | last1 = Servatius | first1 = Brigitte
 | last2 = Christopher | first2 = Peter R.
 | doi = 10.2307/2324184
 | issue = 2
 | journal = The American Mathematical Monthly
 | mr = 1144356
 | pages = 153–158
 | title = Construction of self-dual graphs
 | volume = 99
 | year = 1992}}.</ref>

Az Euler-formulából adódóan minden {{mvar|n}} csúcsú önduális gráfnak pontosan {{math|2''n'' &minus; 2}} éle van.<ref>{{citation|title=Graphs: Theory and Algorithms|first1=K.|last1=Thulasiraman|first2=M. N. S.|last2=Swamy|publisher=John Wiley & Sons|year=2011|isbn=978-1-118-03025-7|url=https://books.google.com/books?id=rFH7eQffQNkC&pg=PA198|at=Exercise&nbsp;7.11, p.&nbsp;198}}.</ref> 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.<ref>See the proof of Theorem 5 in {{harvtxt|Servatius|Christopher|1992}}.</ref>

==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 [[Gráfizomorfizmus|izomorf]],<ref>{{citation|title=Planar Graphs: Theory and Algorithms|series=Dover Books on Mathematics|first1=Takao|last1=Nishizeki|first2=Norishige|last2=Chiba|publisher=Dover Publications|year=2008|isbn=978-0-486-46671-2|url=https://books.google.com/books?id=1Nl4BpacvpwC&pg=PA16|page=16}}.</ref> ezek a párosítások mindig kétirányúak: ha a síkgráf {{mvar|X}} fogalma a duálisban {{mvar|Y}} fogalomnak felel meg, akkor a síkgráf {{mvar|Y}} fogalma éppen a duális {{mvar|X}} fogalmának felel meg.

===Egyszerű gráfok / multigráfok===
Egyszerű gráf duálisa nem feltétlenül egyszerű: tartalmazhat [[hurokél]]eket (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 {{mvar|G}} síkbarajzolható gráfban található [[elválasztó él]]ek (hidak) egy az egyben megfeleltethetők {{mvar|G}} duálisának hurokéleivel.<ref>{{citation|title=Graph Coloring Problems|volume=39|series=Wiley-Interscience Series in Discrete Mathematics and Optimization|first1=Tommy R.|last1=Jensen|first2=Bjarne|last2=Toft|publisher=Wiley|year=1995|isbn=978-0-471-02865-9|page=17|quote=note that "bridge" and "loop" are dual concepts}}.</ref> 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 [[k-szorosan élösszefüggő gráf|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.<ref>{{citation|title=Schaum's Outline of Graph Theory|first=V. K.|last=Balakrishnan|publisher=McGraw Hill Professional|year=1997|isbn=978-0-07-005489-9|at=Problem 8.64, p.&nbsp;229}}.</ref> Ez a gráfosztály magában foglalja a [[k-szorosan összefüggő gráf|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===
[[File:Noniso dual graphs.svg|upright=1.3|thumb|Mindkét piros gráf a kék gráf duálisa, mégsem [[Gráfizomorfizmus|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 [[gráfizomorfizmus|izomorf]] duálisa is létezhet.<ref name="foulds">{{citation|title=Graph Theory Applications|first=L. R.|last=Foulds|publisher=Springer|year=2012|isbn=978-1-4612-0933-1|pages=66–67|url=https://books.google.com/books?id=5G4QBwAAQBAJ&pg=PA66}}.</ref> 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 [[k-szorosan csúcsösszefüggő gráf|3-összefüggő]], akkor a síkbarajzolása (izomorfia erejéig) egyedi, így a duálisa is az.<ref>{{citation
| last1                 = Bondy
| first1                = Adrian | author1-link = John Adrian Bondy
| last2                 = Murty
| first2                = U.S.R. | author2-link = U. S. R. Murty
| title                 = Graph Theory
| url                   = https://books.google.com/books?id=HuDFMwZOwcsC&lpg=PA267
| series                = Graduate Texts in Mathematics
| volume                = 244
| year                  = 2008
| publisher             = Springer
| isbn                  = 978-1-84628-969-9
| lccn                  = 2007923502
| doi                   = 10.1007/978-1-84628-970-5
| at                  = Theorem&nbsp;10.28, p.&nbsp;267
| chapter               = Planar Graphs
}}</ref> A [[Steinitz-tétel]] értelmében ezek a gráfok éppen a [[poliédergráf]]ok, 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 [[Topologikus izomorfia|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 {{math|''K''<sub>2,4</sub>}} [[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áf]]okon [[polinom idő]]ben megoldható a gráfok [[SPQR-fa|SPQR-fája]] segítségével: a közös duálissal rendelkezés [[ekvivalenciareláció]]ja [[kanonikus alak]]já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.<ref>{{citation
 | last1 = Angelini | first1 = Patrizio
 | last2 = Bläsius | first2 = Thomas
 | last3 = Rutter | first3 = Ignaz
 | arxiv = 1303.1640
 | doi = 10.1142/S0218195914600103
 | issue = 4
 | journal = [[International Journal of Computational Geometry and Applications]]
 | mr = 3349917
 | pages = 325–346
 | title = Testing mutual duality of planar graphs
 | volume = 24
 | year = 2014}}.</ref>

===Vágások és körök===
Egy összefüggő gráfon értelmezett [[vágás (gráfelmélet)|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.<ref>{{citation|title=Graph Theory|volume=173|series=Graduate Texts in Mathematics|first=Reinhard|last=Diestel|publisher=Springer|year=2006|isbn=978-3-540-26183-4|page=25|url=https://books.google.com/books?id=aR2TMYQr2CMC&pg=PA25}}.</ref> Egy [[Kör (gráfelmélet)|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.<ref>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}}.</ref>

Ha {{mvar|G}} síkbarajzolható összefüggő gráf, akkor {{mvar|G}} minden egyszerű köre megfelel {{mvar|G}} duálisában egy minimális vágási élhalmaznak, és viszont.<ref>{{citation|title=Algebraic Graph Theory|volume=207|series=[[Graduate Texts in Mathematics]]|first1=Chris|last1=Godsil|author1-link= Chris Godsil|first2=Gordon F.|last2=Royle|author2-link= Gordon Royle |publisher=Springer|year=2013|isbn=978-1-4613-0163-9|at=Theorem&nbsp;14.3.1, p.&nbsp;312|url=https://books.google.com/books?id=GeSPBAAAQBAJ&pg=PA312}}.</ref> Ez a [[Jordan-féle görbetétel]] egy változatának is tekinthető: minden egyszerű kör szétválasztja {{mvar|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.<ref>{{citation|title=Matroid Theory|volume=3|series=Oxford Graduate Texts in Mathematics|first=J. G.|last=Oxley|publisher=Oxford University Press|year=2006|isbn=978-0-19-920250-8|page=93|url=https://books.google.com/books?id=puKta1Hdz-8C&pg=PA93}}.</ref> Egy síkbarajzolható gráf [[Girthparaméter|bősége]] (legkisebb körének mérete) megegyezik duálisának [[k-szorosan élösszefüggő gráf|élösszefüggőségével]] (legkisebb vágás-élhalmazának méretével).<ref name="matgirth"/>

Ez a dualitás az egyedi vágás-élhalmazokról és körökről kiterjeszthető az általuk meghatározott [[vektortér|vektorterekre]] is. Egy gráf [[körtér (gráfelmélet)|körtere]] megegyezik az összes, minden csúcsában páros [[fokszám (gráfelmélet)|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ástér (gráfelmélet)|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.<ref name="hv94"/> Következésképpen, egy síkbarajzolható [[gráf rangja]] (vágásterének [[Hamel-dimenzió]]ja) megegyezik duálisának [[ciklikus rang]]jával (körterének dimenziójával) és viszont.<ref name="foulds"/> Egy gráf [[körbázis]]a olyan egyszerű körök halmaza, melyek a körtér [[Hamel-bázis|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 gráf|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-fa|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ás]]okat 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.<ref name="hv94">{{citation
 | last1 = Hartvigsen | first1 = D.
 | last2 = Mardon | first2 = R.
 | doi = 10.1137/S0895480190177042
 | issue = 3
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | pages = 403–418
 | title = The all-pairs min cut problem and the minimum cycle basis problem on planar graphs
 | volume = 7
 | year = 1994}}.</ref>

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áf]]ok 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ás]]ai (az élekhez olyan irányok rendelése, melyek [[erősen összefüggő gráf]]ot eredményeznek) a [[körmentes irányítás]]ok duálisai (az élekhez olyan irányok rendelése, melyek [[irányított körmentes gráf]]ot eredményeznek).<ref>{{citation
 | last = Noy | first = Marc
 | doi = 10.2307/2695680
 | issue = 1
 | journal = [[American Mathematical Monthly]]
 | mr = 1857074
 | pages = 66–68
 | title = Acyclic and totally cyclic orientations in planar graphs
 | volume = 108
 | year = 2001}}.</ref>

===Feszítőfák===
[[File:Circularmazeexample.jpg|thumb|upright=1|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őfa|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 {{mvar|G}} síkbarajzolható gráf {{mvar|S}} élhalmaza körmentes, akkor az {{mvar|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 {{mvar|S}} összefüggő, akkor az {{mvar|S}} komplementere duálisának élei körmentes részgráfot alkotnak. Az előzőek szerint, ha {{mvar|S}} mindkét tulajdonsággal rendelkezik – összefüggő és körmentes – ugyanez igaz a duális gráf komplementerére. Tehát {{mvar|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á, {{mvar|G}} [[minimális feszítőfa|minimális feszítőfája]] a duális gráf maximális feszítőfájának komplementere.<ref>{{citation
 | last = Tutte | first = W. T. | authorlink = W. T. Tutte
 | isbn = 0-201-13520-5
 | location = Reading, MA
 | mr = 746795
 | page = 289
 | publisher = Addison-Wesley Publishing Company, Advanced Book Program
 | series = Encyclopedia of Mathematics and its Applications
 | title = Graph theory
 | volume = 21
 | year = 1984}}.</ref> A [[legrövidebb utak fája|legrövidebb utak fái]] esetében hasonló módszer nem alkalmazható; a két feszítőfa [[átmérő (gráfelmélet)|á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.<ref>{{citation
 | last1 = Riley | first1 = T. R.
 | last2 = Thurston | first2 = W. P. | author2-link = William Thurston
 | issue = 1
 | journal = Electronic Journal of Combinatorics
 | mr = 2255413
 | page = Note 13, 7
 | title = The absence of efficient dual pairs of spanning trees in planar graphs
 | url = http://www.combinatorics.org/Volume_13/Abstracts/v13i1n13.html
 | volume = 13
 | year = 2006}}.</ref>

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.<ref>{{citation
 | last = Lyons | first = Russell
 | contribution = A bird's-eye view of uniform spanning trees and forests
 | contribution-url = http://www.msri.org/realvideo/ln/msri/2001/percolation/lyons/1/lyons.ps
 | mr = 1630412
 | pages = 135–162
 | publisher = Amer. Math. Soc., Providence, RI
 | series = DIMACS Ser. Discrete Math. Theoret. Comput. Sci.
 | title = Microsurveys in discrete probability (Princeton, NJ, 1997)
 | volume = 41
 | year = 1998}}. See in particular [https://books.google.com/books?id=VAiJNW-5mUgC&pg=PA138 pp.&nbsp;138–139].</ref> Hasonló egybe fonódó fa-párok láthatók a [[vízgyűjtő terület]]ek folyamainak és folyóinak, valamint az őket elválasztó duális gerincvonalak rajzolatában.<ref>{{citation|title=Scaling Behavior for Models of River Network|last=Flammini|first=Alessandro|pages=40–41|url=http://hdl.handle.net/1963/5601|series=Ph.D. thesis|date=October 1996|publisher=[[International School for Advanced Studies]]}}.</ref>

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 {{math|1=''V'' &minus; ''E'' + ''F'' = 2}}, ahol {{mvar|V}} a csúcsok, {{mvar|E}} az élek, {{mvar|F}} pedig a tartományok száma. Bármely feszítőfa és komplementer duális feszítőfája az éleket két, {{math|''V'' &minus; 1}}, illetve {{math|''F'' &minus; 1}} részhalmazra particionálja, a két részhalmaz méretét az egyenlőséghez adva
:{{math|1=''E'' = (''V'' &minus; 1) + (''F'' &minus; 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 [[Karl Georg Christian von Staudt|G. K. C. Von Staudt]] jegyezte fel: ''Geometrie der Lage'' (Nürnberg, 1847).<ref>{{citation|first=D. M. Y.|last=Sommerville|authorlink=Duncan Sommerville|title=An Introduction to the Geometry of N Dimensions|publisher=Dover|year=1958}}.</ref>

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 [[Nemszám|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 csoport]]jának [[Generátorhalmaz|generálására]].<ref>{{citation
 | last = Eppstein | first = David | authorlink = David Eppstein
 | arxiv = cs.DS/0207082
 | contribution = Dynamic generators of topologically embedded graphs
 | pages = 599–608
 | title = Proceedings of the 14th ACM/SIAM Symposium on Discrete Algorithms
 | year = 2003}}.</ref>

===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 [[Frank Harary|Harary]] által megadott, a [[kézfogás-lemma|kézfogás-lemmára]] épülő példa szerint bármely gráfban a csúcsok [[fokszám (gráfelmélet)|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.<ref>{{citation
 | last = Harary | first = Frank | authorlink = Frank Harary
 | location = Reading, Mass.
 | mr = 0256911
 | at = Theorem 9.4, p.&nbsp;142
 | publisher = Addison-Wesley Publishing Co.
 | title = Graph Theory
 | year = 1969}}.</ref>

Síkgráf [[mediális gráf]]ja [[gráfizomorfizmus|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.<ref>{{citation
| editor-last           = Gross
| editor-first          = Jonathan L.
| editor2-last          = Yellen
| editor2-first         = Jay
| title                 = Handbook of Graph Theory
| url                   = https://books.google.com/books?id=mKkIGIea_BkC&lpg=PA724
| year                  = 2003
| publisher             = CRC Press
| isbn                  = 978-1-58488-090-5
| page                  = 724
}}.</ref>

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 gráf|3-reguláris]].<ref>{{citation
 | last = He | first = Xin
 | doi = 10.1137/s0097539796308874
 | issue = 6
 | journal = [[SIAM Journal on Computing]]
 | pages = 2150–2167
 | title = On floor-plan of plane graphs
 | volume = 28
 | year = 1999}}.</ref>

Egy összefüggő síkgráf pontosan akkor tartalmaz [[Euler-út|Euler-utat]] (minden csúcsának fokszáma páros), ha duálisa [[páros gráf]].<ref name="welsh69"/> Egy síkgráf [[Hamilton-kör]]e 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áf]]jai [[fa (gráfelmélet)|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ó.<ref>{{citation
 | last = Florek | first = Jan
 | doi = 10.1016/j.disc.2010.01.018
 | issue = 10–11
 | journal = [[Discrete Mathematics]]
 | mr = 2601261
 | pages = 1531–1535
 | title = On Barnette's conjecture
 | volume = 310
 | year = 2010}}.</ref>

Ha egy {{mvar|G}} síkbarajzolható gráf [[Tutte-polinom]]ja {{math|''T''<sub>''G''</sub>(''x'',''y'')}}, akkor duálisának Tutte-polinomja előállítható az {{mvar|x}} és {{mvar|y}} felcserélésével. Ezért ha a Tutte-polinom valamely speciális értéke {{mvar|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 {{math|''T''<sub>''G''</sub>(0,2)}}, míg a körmentes irányítások száma {{math|''T''<sub>''G''</sub>(2,0)}}.<ref>{{citation
 | last = Las Vergnas | first = Michel | authorlink = Michel Las Vergnas
 | doi = 10.1016/0095-8956(80)90082-9
 | issue = 2
 | journal = [[Journal of Combinatorial Theory]] | series = Series B
 | mr = 586435
 | pages = 231–243
 | title = Convexity in oriented matroids
 | volume = 29
 | year = 1980}}.</ref> A [[hídmentes gráf|hídmentes]] síkbarajzolható gráfok {{mvar|k}} színnel [[gráf színezése|színezése]] megfelel a duális gráf [[sehol sem nulla folyam]]jainak modulo&nbsp;{{mvar|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 {{mvar|k}}-színezések számolhatók (valamely könnyen kiszámítható tényezőig) a {{math|''T''<sub>''G''</sub>(1 &minus; ''k'',0)}} Tutte-polinomértékkel, míg a duális sehol sem nulla {{mvar|k}}-folyamok a {{math|''T''<sub>''G''</sub>(0,1 &minus; ''k'')}} polinomértékkel.<ref>{{cite journal
 | last = Tutte
 | first = William Thomas
 | authorlink = W. T. Tutte
 | year = 1953
 | title = A contribution to the theory of chromatic polynomials
 | url = http://cms.math.ca/cjm/a144778#
}}</ref>

Egy [[st-síkgráf|''st''-síkgráf]] egy összefüggő síkgráf egy hozzátartozó [[bipoláris irányítás]]sal, 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.<ref name="gd"/>

==Variációk==

===Irányított gráfok===
Egy [[irányított gráf|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.<ref name="gd">{{citation
 | last1 = di Battista | first1 = Giuseppe
 | last2 = Eades | first2 = Peter | author2-link = Peter Eades
 | last3 = Tamassia | first3 = Roberto | author3-link = Roberto Tamassia
 | last4 = Tollis | first4 = Ioannis G.
 | isbn = 978-0-13-301615-4
 | page = 91
 | publisher = Prentice Hall
 | title = Graph Drawing: Algorithms for the Visualization of Graphs
 | year = 1999}}.</ref> Ez a szó szoros értelmében nem az irányított síkgráf duálisa, mivel a {{mvar|G}} gráfból kiindulva és az előbb említett műveletet kétszer elvégezve nem az eredeti {{mvar|G}} gráfhoz jutunk vissza, hanem a {{mvar|G}} gráf [[gráf transzponáltja|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 [[gráfbeágyazás|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ő (gráfelmélet)|erdő]]; egy síkgráf pontosan akkor [[Halin-gráf]], ha gyenge duálisa [[kétszeresen összefüggő gráf|kétszeresen összefüggő]] külsíkgráf.

Tekintsünk egy {{mvar|G}} síkgráfot, legyen {{math|''G''<sup>+</sup>}} a következőképpen megkapott sík-multigráf: adjunk egy új {{mvar|v}} csúcsot {{mvar|G}} korlátlan tartományához, majd {{mvar|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 {{mvar|G}} a {{math|''G''<sup>+</sup>}} duálisának gyenge duálisa.<ref>{{citation
 | last1 = Fleischner | first1 = Herbert J.
 | last2 = Geller | first2 = D. P.
 | last3 = Harary | first3 = Frank | author3-link = Frank Harary
 | mr = 0389672
 | journal = Journal of the Indian Mathematical Society
 | pages = 215–219
 | title = Outerplanar graphs and weak duals
 | volume = 38
 | year = 1974}}.</ref><ref>{{citation
 | last1 = Sysło | first1 = Maciej M.
 | last2 = Proskurowski | first2 = Andrzej
 | contribution = On Halin graphs
 | doi = 10.1007/BFb0071635
 | pages = 248–256
 | publisher = Springer-Verlag
 | series = Lecture Notes in Mathematics
 | title = Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981
 | volume = 1018
 | year = 1983}}.</ref>

===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áf]]okon 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 [[tesszaláció|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.<ref>{{mathworld|id=DualTessellation|title=Dual Tessellation}}</ref>

[[File:Delaunay Voronoi.svg|thumb|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-diagram]]ja a sík olyan [[sokszög]]ekre felosztása, melyben lévő pontok közelebb vannak az adott sokszög generátorpontjához, mint a többiéhez. A bemenet [[konvex burok|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élegyenes]]ek. A Voronoj-diagram duálisa a bemenet [[Delaunay-háromszögelés]]e, 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 [[Ideális térelemek|a végtelenben lévő]] mesterséges csúcsot a Voronoj-diagramhoz, hogy az összes félegyenes végpontjául szolgáljon,<ref>{{citation|title=Foundations of Multidimensional and Metric Data Structures|first=Hanan|last=Samet|authorlink=Hanan Samet|publisher=Morgan Kaufmann|year=2006|isbn=978-0-12-369446-1|page=348|url=https://books.google.com/books?id=vO-NRRKHG84C&pg=PA348}}.</ref> 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===
{{több kép|align=right|szélesség1=192|kép1=Heawood graph and K7 dually embedded in the torus.svg|szöveg1=A {{math|''K''<sub>7</sub>}} a [[Heawood-gráf]] duálisa a [[tórusz]]on|szélesség2=220|kép2=K6-Petersen duality.svg|szöveg2=A {{math|''K''<sub>6</sub>}} a [[Petersen-gráf]] duálisa a [[projektív sík]]on}}
A dualitás fogalma kiterjeszthető a síkon kívül más, kétdimenziós [[sokaság (matematika)|sokaságokba]] történő [[gráf beágyazás|beágyazásokra]] is. A definíció ugyanaz: a sokaságba ágyazott gráf [[komplementerképzés|komplementerének]] minden [[összefüggő tér|ö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 {{math|''K''<sub>7</sub>}} [[teljes gráf]] [[tóruszra rajzolható 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.<ref name="cubo">{{citation
 | last1 = Gagarin
 | first1 = Andrei
 | last2 = Kocay
 | first2 = William
 | author2-link = William Lawrence Kocay
 | last3 = Neilson
 | first3 = Daniel
 | journal = Cubo
 | pages = 351–371
 | title = Embeddings of small graphs on the torus
 | url = http://www.cs.rhul.ac.uk/home/agagarin/Embeddings.pdf
 | volume = 5
 | year = 2003
 | accessdate = 2017-04-17
 | archívurl = https://web.archive.org/web/20170201102452/http://www.cs.rhul.ac.uk/home/agagarin/Embeddings.pdf
 | archívdátum = 2017-02-01
 }}.</ref>

Ugyanaz az elgondolás kiválóan működik [[irányíthatóság|nem irányítható felületek]] esetében is. Például a {{math|''K''<sub>6</sub>}} beágyazható a [[projektív sík]]ba tíz háromszögű tartománnyal [[félikozaéder]]ként, duálisa pedig a [[Petersen-gráf]], beágyazva mint [[féldodekaéder]].<ref>{{citation
 | last1 = Nakamoto | first1 = Atsuhiro
 | last2 = Negami | first2 = Seiya
 | issue = 1
 | journal = Memoirs of Osaka Kyoiku University
 | mr = 1833214
 | pages = 1–15
 | title = Full-symmetric embeddings of graphs on closed surfaces
 | volume = 49
 | year = 2000}}.</ref>

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ög]]e (a kocka két szemközti csúcsának eltávolításával kapott hatszögek) a kocka [[tórusz]]ba á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 {{math|''K''<sub>4</sub>}} [[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.<ref name="cubo"/>

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ő {{mvar|G}} gráf '''algebrai duálisa''' olyan {{math|''G''<sup>★</sup>}} gráf, melyre igaz, hogy {{mvar|G}} és {{math|''G''<sup>★</sup>}} élhalmaza megegyezik, {{mvar|G}} bármely [[körtér (gráfelmélet)|köre]] {{math|''G''<sup>★</sup>}} egy [[vágás (gráfelmélet)|vágása]] és {{mvar|G}} bármely vágása {{math|''G''<sup>★</sup>}} 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érium]]ban:<ref>{{citation
 | last = Whitney | first = Hassler | author-link = Hassler Whitney
 | journal = Transactions of the American Mathematical Society
 | pages = 339–362
 | title = Non-separable and planar graphs
 | volume = 34
 |number=2
 |doi=10.1090/S0002-9947-1932-1501641-2
 | year = 1932}}.</ref>

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

Ugyanez a tény kifejezhető a [[matroid]]ok elméletének felhasználásával is. Ha {{mvar|M}} a {{mvar|G}} gráf [[grafikus matroid]]ja, akkor a {{math|''G''<sup>★</sup>}} gráf pontosan akkor a {{mvar|G}} algebrai duálisa, ha {{math|''G''<sup>★</sup>}} grafikus matroidja éppen az {{mvar|M}} [[duális matroid]]ja. Ekkor Whitney síkgráfkritériuma átfogalmazható úgy, hogy az {{mvar|M}} grafikus matroid duális matroidja pontosan akkor maga is grafikus matroid, ha az {{mvar|M}} alapjául szolgáló {{mvar|G}} gráf síkbarajzolható. Ha {{mvar|G}} síkbarajzolható, a duális matroid a {{mvar|G}} duálisának grafikus matroidja. További következmény, hogy {{mvar|G}} összes síkbarajzolásához tartozó duálisoknak izomorfak a grafikus matroidjaik.<ref>{{citation|title=Matroid Theory|volume=3|series=Oxford graduate texts in mathematics|first=J. G.|last=Oxley|authorlink=James Oxley|publisher=Oxford University Press|year=2006|isbn=978-0-19-920250-8|contribution=5.2 Duality in graphic matroids|page=143|contribution-url=https://books.google.com/books?id=puKta1Hdz-8C&pg=PA143}}.</ref>

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ó {{mvar|G}} gráf duális matroidja maga nem grafikus matroid. Mindazonáltal egy olyan matroid, melynek körei megfelelnek {{mvar|G}} vágásainak, és ebben az értelemben tekinthető a {{mvar|G}} általánosított algebrai duálisának.<ref>{{citation|title=Graph Theory As I Have Known It|volume=11|series=Oxford Lecture Series in Mathematics and Its Applications|first=W. T.|last=Tutte|authorlink=W. T. Tutte|publisher=Oxford University Press|year=2012|isbn=978-0-19-966055-1|page=87|url=https://books.google.com/books?id=uYW2tttqQ74C&pg=PA87}}.</ref>

Az Euler-utat tartalmazó és a páros síkbarajzolható gráfok közötti dualitás kiterjeszthető a [[bináris matroid]]okra (melyek magukban foglalják a síkbarajzolható gráfok [[grafikus matroid]]jait): egy bináris matroid pontosan akkor [[Euler-matroid|Euler-féle]], ha duális matroidja [[páros matroid|páros]].<ref name="welsh69">{{citation
 | last = Welsh | first = D. J. A. | authorlink = Dominic Welsh
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 0237368
 | pages = 375–377
 | title = Euler and bipartite matroids
 | volume = 6
 | year = 1969
 | doi=10.1016/s0021-9800(69)80033-5}}.</ref> A [[girthparaméter]] és [[élösszefüggőség]] duális fogalmait a matroidelmélet a [[matroid girthparamétere|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.<ref name="matgirth">{{citation
 | last1 = Cho | first1 = Jung Jin
 | last2 = Chen | first2 = Yong
 | last3 = Ding | first3 = Yu
 | doi = 10.1016/j.dam.2007.06.015
 | issue = 18
 | journal = Discrete Applied Mathematics
 | mr = 2365057
 | pages = 2456–2470
 | title = On the (co)girth of a connected matroid
 | volume = 155
 | year = 2007}}.</ref>

==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 rendszer]]ekben 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.<ref>{{citation|title=Integrated Models in Geography|first1=Richard J.|last1=Chorley|first2=Peter|last2=Haggett|publisher=Routledge|year=2013|isbn=978-1-135-12184-6|page=646|url=https://books.google.com/books?id=8c79AQAAQBAJ&pg=PA646}}.</ref>

A [[számítógépes látás]] területén a digitális képeket apró, négyzetes [[pixel]]ekre 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.<ref>{{citation|title=Applied Graph Theory in Computer Vision and Pattern Recognition|volume=52|series=Studies in Computational Intelligence|first1=Abraham|last1=Kandel|first2=Horst|last2=Bunke|first3=Mark|last3=Last|publisher=Springer|year=2007|isbn=978-3-540-68020-8|page=16|url=https://books.google.com/books?id=C8tuCQAAQBAJ&pg=PA16}}.</ref>

A [[számítási geometria]] területén a [[Voronoj-diagram]]ok és [[Delaunay-háromszögelés]]ek 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.<ref>{{citation|title=Discrete and Computational Geometry|first1=Satyan L.|last1=Devadoss|author1-link=Satyan Devadoss|first2=Joseph|last2=O'Rourke|author2-link=Joseph O'Rourke (professor)|publisher=Princeton University Press|year=2011|isbn=978-1-4008-3898-1|page=111|url=https://books.google.com/books?id=InJL6iAaIQQC&pg=PA111}}.</ref> Ugyanez a dualitás felhasználható a [[végeselemes módszer|végeselemes]] [[hálógenerálás]]ra is. A Voronoj-diagramokon alapuló, ponthalmazok a felületen egyenletesebb távolságeloszlású helyzetbe mozgatására szolgáló [[Lloyd-algoritmus]]t 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.<ref>{{citation
 | last1 = Du | first1 = Qiang
 | last2 = Gunzburger | first2 = Max
 | doi = 10.1016/S0096-3003(01)00260-0
 | issue = 2–3
 | journal = Applied Mathematics and Computation
 | pages = 591–607
 | title = Grid generation and optimization based on centroidal Voronoi tessellations
 | volume = 133
 | year = 2002}}.</ref>

A [[CMOS]] áramkörök [[logikai szintézis]]e során a szintetizálandó függvény [[Boole-algebra (informatika)|Boole-algebrai]] kifejezés formájában szerepel. Később ezt a kifejezést átalakítják két [[soros-párhuzamos gráf|soros-párhuzamos multigráffá]]. Ezek a gráfok [[kapcsolási rajz]]ként értelmezhetők, melyben a gráfok élei [[tranzisztor]]okat 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ő.<ref>{{citation|title=Low-Power Electronics Design|first=Christian|last=Piguet|publisher=CRC Press|year=2004|isbn=978-1-4200-3955-9|contribution=7.2.1 Static CMOS Logic|pages=7-1–7-2|url=https://books.google.com/books?id=QzKfa_Y4IuIC&pg=SA7-PA1}}.</ref> 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.<ref>{{citation|title=Digital Integrated Circuit Design: From VLSI Architectures to CMOS Fabrication|first=Hubert|last=Kaeslin|publisher=Cambridge University Press|year=2008|isbn=978-0-521-88267-5|contribution=8.1.4 Composite or complex gates|page=399|url=https://books.google.com/books?id=gdRStcYgf2oC&pg=PA399}}.</ref>

==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.<ref>{{citation|title=Euler's Gem: The Polyhedron Formula and the Birth of Topology|first=David S.|last=Richeson|publisher=Princeton University Press|year=2012|isbn=978-1-4008-3856-1|pages=58–61|url=https://books.google.com/books?id=KUYLhOVkaV4C&pg=PA58}}.</ref>
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ája|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-diagram]]ok közé sorolják.<ref>{{citation|title=Funicular Shell Design: Geometric Approaches to Form Finding and Fabrication of Discrete Funicular Structures|last=Rippmann|first=Matthias|series=[[Habilitation]] thesis, Diss. ETH No. 23307|publisher=[[ETH Zurich]]|year=2016|doi=10.3929/ethz-a-010656780|pages=39–40}}. Lásd még {{citation|last=Erickson|first=Jeff|url=https://plus.google.com/+JeffErickson/posts/6UyRPX7ShXV|title=Reciprocal force diagrams from ''Nouvelle Méchanique ou Statique'' by Pierre de Varignon (1725)|date=June 9, 2016|quote=Is this the oldest illustration of duality between planar graphs?}}.</ref> A [[négyszíntétel|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.<ref>{{citation|title=Graph Theory, 1736–1936|first1=Norman|last1=Biggs|author1-link=Norman L. Biggs|first2=E. Keith|last2=Lloyd|first3=Robin J.|last3=Wilson|author3-link=Robin Wilson (mathematician)|publisher=Oxford University Press|year=1998|page=118|isbn=978-0-19-853916-2|url=https://books.google.com/books?id=XqYTk0sXmpoC&pg=PA118}}.</ref> A dualitás, mint absztrakt síkgráfokon értelmezett művelet 1931-ben [[Hassler Whitney]]-nél jelenik meg.<ref>{{citation | last = Whitney | first = Hassler | authorlink = Hassler Whitney | doi = 10.2307/1968197 | issue = 2 | journal = [[Annals of Mathematics]] | mr = 1503003 | pages = 378–390 | series = Second Series | title = A theorem on graphs | volume = 32 | year = 1931}}.</ref>

== Jegyzetek ==
{{reflist|30em}}

==További információk==
* {{mathworld | urlname = DualGraph | title = Dual graph}}

== Fordítás ==
{{fordítás|en|Dual graph|oldid=750599169|n=a|4=angol}}

{{portál|Matematika}}

[[Kategória:Gráfelmélet]]
[[Kategória:Síkgráfok]]
[[Kategória:Algebrai gráfelmélet]]
[[Kategória:Topologikus gráfelmélet]]
[[Kategória:Gráfműveletek]]