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

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

• 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)

Рёберная раскраска

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

Версия теоремы Визинга утверждает, что любой мультиграф с максимальной степенью ${\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: . Lecture notes 2006, p. 242 (German)