imported>Aka: /* Weblinks */ Dateigröße angepasst

2021-11-05T16:08:29Z

Weblinks: Dateigröße angepasst

Neue Seite

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 <math>\left\lfloor \tfrac{n}{2} \right\rfloor </math>, <math>\left\lfloor \tfrac{n}{2} \right\rfloor </math> und <math>\left\lfloor \tfrac{n+1}{2} \right\rfloor </math> Kanten verbunden sind.

Für gerade <math>n</math> 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.

<gallery widths="100" heights="100" perrow="7" caption="Shannonsche Multigraphen">
Datei:Shannon multigraph 2.svg|<math>Sh(2)</math>
Datei:Shannon multigraph 3.svg|<math>Sh(3)</math>
Datei:Shannon multigraph 4.svg|<math>Sh(4)</math>
Datei:Shannon multigraph 5.svg|<math>Sh(5)</math>
Datei:Shannon multigraph 6.svg|<math>Sh(6)</math>
Datei:Shannon multigraph 7.svg|<math>Sh(7)</math>
</gallery>

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

== Weblinks ==
{{commonscat|Shannon multigraphs}}
* Lutz Volkmann: ''[https://www.math2.rwth-aachen.de/files/gt/buch/graphen_an_allen_ecken_und_kanten.pdf Graphen an allen Ecken und Kanten] (PDF; 3,5 MB)''. Skript 2006, S. 242

[[Kategorie:Graphenklasse]]

Shannon-Multigraph - Versionsgeschichte

imported>Aka: /* Weblinks */ Dateigröße angepasst