Multigraf Shannona

W matematycznej dyscyplinie teorii grafów multigrafy Shannona , nazwane na cześć Claude'a Shannona przez Vizinga (1965) , są specjalnym typem grafów trójkątnych, które są używane w szczególności w dziedzinie kolorowania krawędzi .

Multigraf Shannona to multigraf z 3 wierzchołkami, dla których spełniony jest jeden z poniższych warunków:

• a) wszystkie 3 wierzchołki są połączone taką samą liczbą krawędzi.
• b) jak w a) i dodaje się jedną dodatkową krawędź.

Dokładniej mówi się o multigrafie Shannona Sh ( n ) ${\ Displaystyle \ lewo \ lfloor {\ Frac {n} {2}} \ prawo \ rfloor}$ jeśli trzy wierzchołki są połączone przez $}$ Displaystyle \ lewo \ lfloor { i ${\ Displaystyle \ lewo \ lfloor {\ Frac {n + 1} {2}} \ prawo \rfloor }$ odpowiednio krawędzie. Ten multigraf ma maksymalny stopień n . Jego krotność (maksymalna liczba krawędzi w zbiorze krawędzi, z których wszystkie mają te same punkty końcowe) wynosi ${\ Displaystyle \ lewo \ lfloor {\ Frac {n + 1} {2}} \ prawo \ rfloor }$ .

Przykłady

• Multigrafy Shannona
• 

  Sz(2)

• 

  Sz(3)

• 

  Sz(4)

• 

  Sz(5)

• 

  Sz(6)

• 

  Sz(7)

Kolorystyka krawędzi

Ten dziewięciokrawędziowy multigraf Shannona wymaga dziewięciu kolorów w dowolnej kolorystyce krawędzi; jego stopień wierzchołka wynosi sześć, a krotność to trzy.

Zgodnie z twierdzeniem Shannona (1949) każdy multigraf o maksymalnym stopniu ma kolorowanie krawędzi, które wykorzystuje co najwyżej kolory ${\ Frac {3} {2}} \ Delta$$Displaystyle$ . Kiedy $parzysta$$,$ przykład multigrafu Shannona z krotnością , że ta granica jest ścisła: stopień wierzchołka jest dokładnie $Delta}$ , ale każdy z ${2}} \ Delta}$$Frac$ krawędzie przylegają do każdej innej krawędzi, więc kolorów dowolne odpowiednie zabarwienie krawędzi.

Wersja twierdzenia Vizinga ( Vizing 1964 $Displaystyle \ Delta + \ mu}$ stwierdza, że ​​​​każdy multigraf z maksymalnym stopniem $może$ być pokolorowany przy użyciu co najwyżej $\$ zabarwienie. Ponownie, ta granica jest wąska dla multigrafów Shannona.

•    Fiorini S.; Wilson, Robin James (1977), Kolorowanie krawędzi wykresów , Research Notes in Mathematics, tom. 16, Londyn: Pitman, s. 34, ISBN 0-273-01129-4 , MR 0543798
•   Shannon, Claude E. (1949), „Twierdzenie o kolorowaniu linii sieci”, J. Math. Physics , 28 : 148–151, doi : 10.1002/sapm1949281148 , hdl : 10338.dmlcz/101098 , MR 0030203 .
•   Volkmann, Lutz (1996), Fundamente der Graphentheorie (w języku niemieckim), Wien: Springer, s. 289, ISBN 3-211-82774-9 .
•   Vizing, VG (1964), „O oszacowaniu klasy chromatycznej wykresu p ”, Diskret. Analizuj. , 3 : 25–30, MR 0180505 .
•   Vizing, VG (1965), „Klasa chromatyczna multigrafu”, Kibernetika , 1965 (3): 29–39, MR 0189915 .

Linki zewnętrzne

• Lutz Volkmann: Graphen an allen Ecken und Kanten . Notatki z wykładu 2006, s. 242 (niemiecki)