Multigraf Shannon

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 25 decembrie 2019; verificările necesită 3 modificări .

În teoria grafurilor, multigrafele Shannon sunt un tip special de grafuri triunghiulare care sunt utilizate în studiul colorării marginilor . Withing a numit aceste grafice după Claude Shannon [1] .

Multigrafele Shannon sunt multigrafe cu trei vârfuri care îndeplinesc una dintre următoarele condiții:

a) toate cele trei vârfuri sunt legate prin același număr de muchii.
b) la fel ca în a) dar se mai adaugă o muchie.

Mai precis, un graf este un multigraf Shannon dacă trei vârfuri sunt conectate prin , și , respectiv, prin muchii. Acest multigraf are un grad maxim de . Multiplicitatea sa (numărul maxim de muchii care au aceleași capete) este . $Sh(n)$ $\left\lfloor {\frac {n}{2}}\right\rfloor$ $\left\lfloor {\frac {n}{2}}\right\rfloor$ $\left\lfloor {\frac {n+1}{2}}\right\rfloor$ $n$ $\left\lfloor {\frac {n+1}{2}}\right\rfloor$

Exemple

Shannon multigrafe
Sh(2)
Sh(3)
Sh(4)
Sh(5)
Sh(6)
Sh(7)

Colorarea marginilor

Conform teoremei lui Shannon [2] , orice multigraf cu grad maxim are o colorare a muchiei folosind culorile maxime. Dacă numărul este par, exemplul multigrafului Shannon cu multiplicitate arată că această limită este exactă: gradul vârfului este exact egal, dar fiecare dintre muchii este conjugată cu orice altă muchie, deci culorile sunt necesare pentru orice muchie adecvată . colorare. $\Delta$ ${\frac {3}{2}}\Delta$ $\Delta$ $\Delta /2$ $\Delta ,$ ${\frac {3}{2}}\Delta$ ${\frac {3}{2}}\Delta$

O versiune a teoremei lui Vizing [3] afirmă că orice multigraf cu grad și multiplicitate maxime poate fi colorat folosind cel mult culori. Din nou, această limită este exactă pentru multigrafele Shannon. $\Delta$ $\mu$ $\Delta +\mu$

Note

↑ V. G. Vizing. Despre estimarea clasei cromatice a unui p-graf // Sat. Analiză discretă. - 1964. - T. 3. - S. 25-30.
↑ Claude E. Shannon. O teoremă privind colorarea liniilor unei rețele // J. Math. Fizică. - 1949. - T. 28. - S. 148-151.
↑ V. G. Vizing. Clasa cromatică a unui multigraf // Cibernetică. - 1965. - Emisiune. 3. - S. 29-39.

Literatură

S. Fiorini, RJ Wilson. Colorarea marginilor graficelor. - Londra: Pitman, 1977. - V. 16. - P. 34. - (Research Notes in Mathematics). - ISBN 0-273-01129-4 .
Lutz Volkmann. Fundamente der Graphentheorie (neopr.) . - Wien: Springer, 1996. - P. 289. - ISBN 3-211-82774-9 .

Link -uri

Lutz Volkmann: Graphen an allen Ecken und Kanten . Note de curs 2006, p. 242 (germană)