Shannon-Multigraph

Mit Shannon-Multigraph o​der auch Shannonscher Multigraph (nach Claude Elwood Shannon) bezeichnet m​an eine spezielle Sorte v​on Graphen i​n der Graphentheorie, s​ie sind d​ort vor a​llem in d​er Theorie d​er Kantenfärbungen v​on Bedeutung.

Ein Multigraph mit drei Ecken, die mit jeweils mit der gleichen Anzahl von Kanten verbunden sind oder darüber hinaus noch eine weitere zusätzliche Kante besitzt, wird als Shannon-Multigraph bezeichnet. Etwas genauer spricht man von dem Shannon-Multigraph Sh(n), wenn die drei Ecken durch ${\displaystyle \left\lfloor {\tfrac {n}{2}}\right\rfloor }$, ${\displaystyle \left\lfloor {\tfrac {n}{2}}\right\rfloor }$ und ${\displaystyle \left\lfloor {\tfrac {n+1}{2}}\right\rfloor }$ Kanten verbunden sind.

Für gerade ${\displaystyle n}$ nimmt der Shannon-Multigraph die obere Grenze im Satz von Vizing und im Satz von Shannon an und weist somit nach, dass diese Abschätzungen in einem gewissen Sinne optimal sind.

• Shannonsche Multigraphen
• 
  ${\displaystyle Sh(2)}$
• 
  ${\displaystyle Sh(3)}$
• 
  ${\displaystyle Sh(4)}$
• 
  ${\displaystyle Sh(5)}$
• 
  ${\displaystyle Sh(6)}$
• 
  ${\displaystyle Sh(7)}$

Literatur

• Lutz Volkmann: Fundamente der Graphentheorie, Springer (Wien) 1996, ISBN 3-211-82774-9, S. 289

Weblinks

• Lutz Volkmann: Graphen an allen Ecken und Kanten (PDF; 3,5 MB). Skript 2006, S. 242