duális gráf
Magyar
Kiejtés
- IPA: [ ˈduaːliʒɡraːf]
Főnév
duális gráf (matematika, gráfelmélet) 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.
Fordítások
|