Shannon-Multigraph

Mit Shannon-Multigraph oder auch Shannonscher Multigraph (nach Claude Elwood Shannon) bezeichnet man eine spezielle Sorte von Graphen in der Graphentheorie, sie sind dort vor allem in der Theorie der Kantenfärbungen von 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 $\left\lfloor {\tfrac {n}{2}}\right\rfloor$ , $\left\lfloor {\tfrac {n}{2}}\right\rfloor$ und $\left\lfloor {\tfrac {n+1}{2}}\right\rfloor$ Kanten verbunden sind.

Für gerade $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.