В теории графов мультиграфами Шеннона называется специальный вид треугольных графов, которые используются при исследовании рёберной раскраски. Визинг назвал эти графы в честь Клода Шеннона^[1].

Мультиграфы Шеннона — это мультиграфы с тремя вершинами, для которых выполняется одно из следующих условий:

• a) все три вершины соединены одним и тем же числом рёбер.
• b) так же, как в a) но добавлено ещё одно дополнительное ребро.

Говоря точнее, граф является мультиграфом Шеннона ${\displaystyle Sh(n)}$, если три вершины соединены ${\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 n}$. Его кратность (максимальное число рёбер, имеющих те же самые концы) равна ${\displaystyle \left\lfloor {\frac {n+1}{2}}\right\rfloor }$.

• мультиграфы Шеннона
• 
  Sh(2)
• 
  Sh(3)
• 
  Sh(4)
• 
  Sh(5)
• 
  Sh(6)
• 
  Sh(7)

Согласно теореме Шеннона^[2], любой мультиграф с максимальной степенью ${\displaystyle \Delta }$ имеет рёберную раскраску, использующую максимум ${\displaystyle {\frac {3}{2}}\Delta }$ цветов. Если число ${\displaystyle \Delta }$ чётно, пример мультиграфа Шеннона с кратностью ${\displaystyle \Delta /2}$ показывает, что эта граница точна: степень вершины в точности равна ${\displaystyle \Delta ,}$ но каждое из ${\displaystyle {\frac {3}{2}}\Delta }$ рёбер сопряжено с любым другим ребром, так что требуется ${\displaystyle {\frac {3}{2}}\Delta }$ цветов для любой правильной рёберной раскраски.

Версия теоремы Визинга^[3] утверждает, что любой мультиграф с максимальной степенью ${\displaystyle \Delta }$ и кратностью ${\displaystyle \mu }$ можно раскрасить используя не более ${\displaystyle \Delta +\mu }$ цветов. Снова, эта граница точна для мультиграфов Шеннона.

• S. Fiorini, R. J. Wilson. Edge-colourings of graphs. — London: Pitman, 1977. — Т. 16. — С. 34. — (Research Notes in Mathematics). — ISBN 0-273-01129-4.
• Lutz Volkmann. Fundamente der Graphentheorie (неопр.). — Wien: Springer, 1996. — С. 289. — ISBN 3-211-82774-9.

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

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.