Grafic dual
Dualul unui graf plan este un graf în care vârfurile corespund fețelor grafului ; două vârfuri sunt conectate printr-o muchie dacă și numai dacă fețele corespunzătoare ale graficului au o muchie comună. De exemplu, graficele cubului și octaedrul sunt duale unul față de celălalt .
Termenul dual este folosit deoarece această proprietate este simetrică - dacă H este dual cu G , atunci G este dual cu H (presupunând că G este conectat ). Aceeași noțiune poate fi folosită pentru a încorpora grafice în varietăți . Noțiunea de dualitate de graf este diferită de dualitatea muchie-vârf ( line graph ) a unui graf și cele două nu trebuie confundate.
Proprietăți
- Graficul dual este un pseudograf : poate avea bucle și margini multiple.
- Dualul unui graf plan este un multigraf plan .
- Dacă G este un graf conex și dacă G ′ este dualul lui G , atunci G este dualul lui G ′.
- Deoarece graficul dual depinde de metoda de stivuire , pot exista mai multe duale (neizomorfe) la același graf plan . În figură, graficele roșii nu sunt izomorfe deoarece cel de sus are gradul 6 (fața exterioară). Totuși, dacă graficul este 3-conectat , așa cum a arătat Whitney , pliul este unic și, prin urmare, graficul dual este, de asemenea, unic [1] .
Datorită dualității, pentru orice rezultat folosind numărul de fețe și vârfuri, aceste valori pot fi schimbate.
Se spune că un grafic este auto-dual dacă este izomorf cu graficul său dual. De exemplu, graficul tetraedric este auto-dual .
Dualitate algebrică
Fie G un graf conex. Se spune că un grafic G ★ este algebric dual cu un grafic G astfel încât G și G ★ au același set de muchii, orice ciclu din G este o tăietură a lui G ★ și orice tăietură a lui G este un ciclu în G ★ . Orice graf plan are un graf algebric dual, care nu este unic în cazul general (graful dual este determinat de stivuire). Reversul este de asemenea adevărat – așa cum a arătat Hassler în criteriul său de planaritate [2] , un graf conex este plan dacă și numai dacă are un graf algebric dual.
Același fapt poate fi exprimat în termenii teoriei matroidelor : dacă M este matroida grafică a unui grafic G , atunci matroida duală M este matroida grafică dacă și numai dacă G este plană. Dacă G este planar, atunci matroida duală este matroida grafică a graficului dual al lui G.
Dualitate slabă
Slab dual la un graf plan este un subgraf al grafului dual în care vârfurile corespund fețelor mărginite ale grafului original. Un graf planar este exterior planar dacă și numai dacă dualul său este o pădure , iar un graf planar este un graf Halin dacă și numai dacă dualul său slab este dublu conectat și exterior. Pentru orice graf plan G , fie G + un multigraf plan format prin adăugarea unui singur vârf v la o față nemărginită a lui G și conectarea v la toate vârfurile feței exterioare (de câteva ori dacă vârful apare de mai multe ori la limita față). Acum G este dualul slab al dualului (planar) al lui G + graficul [3] [4] .
Note
- ↑ Adrian Bondy, USR Murty. capitolul „Grafe planare”, Teorema 10.28 // Teoria graficelor. - Springer, 2008. - V. 244. - P. 267. - (Texte de absolvire a matematicii). — ISBN 9781846289699 . - doi : 10.1007/978-1-84628-970-5 .
- ↑ Hassler Whitney. Grafice neseparabile și plane // Tranzacții ale Societății Americane de Matematică. - 1932. - T. 34 , nr. 2 . — S. 339–362 . - doi : 10.1090/S0002-9947-1932-1501641-2 .
- ↑ Herbert J. Fleischner, D.P. Geller, Frank Harary. Grafice exterioare și duale slabe // Journal of the Indian Mathematical Society. - 1974. - T. 38 . — S. 215–219 .
- ↑ Maciej M. Sysło, Andrzej Proskurowski. Teoria graficelor: Actele unei conferințe ținute la Lagów, Polonia, 10–13 februarie 1981. - Springer-Verlag, 1983. - Vol. 1018. - P. 248-256. — (Note de curs la matematică). - doi : 10.1007/BFb0071635 .
Link -uri
- Weisstein, Eric W. Dual graph (engleză) pe site-ul web Wolfram MathWorld .
- Weisstein, Eric W. Self-dual graph (engleză) pe site-ul Wolfram MathWorld .