Shannon Multigraph - Shannon multigraph

In der mathematischen Disziplin der Graphentheorie , Shannon Multigraphen , benannt nach Claude Shannon durch Vizing (1965) , ist eine besondere Art von Dreieck Graphen , die auf dem Gebiet der Verwendung von Kantenfärbung im Besonderen.

Ein Shannon-Multigraph ist ein Multigraph mit 3 Eckpunkten, für die eine der folgenden Bedingungen gilt:

• a) Alle 3 Eckpunkte sind durch die gleiche Anzahl von Kanten verbunden.
• b) wie in a) und eine zusätzliche Kante wird hinzugefügt.

Genauer gesagt spricht man von Shannon Multigraph Sh ( n ) , wenn die drei Scheitelpunkte durch verbunden sind , und die Kanten sind. Dieser Multigraph hat den maximalen Grad n . Die Multiplizität (die maximale Anzahl von Kanten in einer Reihe von Kanten, die alle dieselben Endpunkte haben) beträgt . ${\ displaystyle \ left \ lfloor {\ frac {n} {2}} \ right \ rfloor}$${\ displaystyle \ left \ lfloor {\ frac {n} {2}} \ right \ rfloor}$${\ displaystyle \ left \ lfloor {\ frac {n + 1} {2}} \ right \ rfloor}$ ${\ displaystyle \ left \ lfloor {\ frac {n + 1} {2}} \ right \ rfloor}$

Beispiele

• Shannon Multigraphen
• 

  Sh (2)

• 

  Sh (3)

• 

  Sh (4)

• 

  Sh (5)

• 

  Sh (6)

• 

  Sh (7)

Kantenfärbung

Dieser Shannon-Multigraph mit neun Kanten erfordert neun Farben in jeder Kantenfarbe. sein Scheitelpunktgrad ist sechs und seine Multiplizität ist drei.

Nach einem Satz von Shannon (1949) hat jeder Multigraph mit maximalem Grad eine Kantenfarbe, die höchstens Farben verwendet. Wenn gerade ist, zeigt das Beispiel des Shannon-Multigraphs mit Multiplizität , dass diese Grenze eng ist: Der Scheitelpunktgrad ist genau , aber jede der Kanten grenzt an jede andere Kante, sodass Farben in jeder richtigen Kantenfarbe erforderlich sind. ${\ displaystyle \ Delta}$${\ displaystyle {\ frac {3} {2}} \ Delta}$${\ displaystyle \ Delta}$${\ displaystyle \ Delta / 2}$${\ displaystyle \ Delta}$${\ displaystyle {\ frac {3} {2}} \ Delta}$${\ displaystyle {\ frac {3} {2}} \ Delta}$

Eine Version des Satzes von Vizing ( Vizing 1964 ) besagt, dass jeder Multigraph mit maximalem Grad und Multiplizität mit höchstens Farben gefärbt werden darf . Auch diese Grenze ist für die Shannon-Multigraphen eng. ${\ displaystyle \ Delta}$${\ displaystyle \ mu}$${\ displaystyle \ Delta + \ mu}$

Verweise

• Fiorini, S.; Wilson, Robin James (1977), Kantenfärbungen von Graphen , Research Notes in Mathematics, 16 , London: Pitman, p. 34, ISBN 0-273-01129-4, MR  0543798
• Shannon, Claude E. (1949), "Ein Satz über das Färben der Linien eines Netzwerks", J. Math. Physics , 28 : 148–151, doi : 10.1002 / sapm1949281148 , hdl : 10338.dmlcz / 101098 , MR  0030203.
• Volkmann, Lutz (1996), Fundamente der Graphentheorie , Wien: Springer, p. 289, ISBN 3-211-82774-9.
• Vizing, VG (1964), "Nach einer Schätzung der chromatischen Klasse eines p- Graphen", Diskret. Analiz. , 3 : 25-30, MR  0.180.505.
• Vizing, VG (1965), "Die chromatische Klasse eines Multigraphen", Kibernetika , 1965 (3): 29–39, MR  0189915.

Externe Links

• Lutz Volkmann: Graphen an allen Ecken und Kanten . Lecture Notes 2006, p. 242 (deutsch)