Shannon-Multigraph

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 \frac{n}{2} \right\rfloor , \left\lfloor \frac{n}{2} \right\rfloor und \left\lfloor \frac{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.


Literatur

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

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Edge coloring — A 3 edge coloring of the Desargues graph. In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge… …   Wikipedia

  • Line graph — This article is about the mathematical concept. For statistical presentation method, see line chart. In graph theory, the line graph L(G) of undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The name… …   Wikipedia

  • Pseudoforest — A 1 forest (a maximal pseudoforest), formed by three 1 trees In graph theory, a pseudoforest is an undirected graph[1] in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of ve …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”