Мультиграф Шеннона

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

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

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

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

Примеры

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

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

Для рёберной раскраски мультиграфа Шеннона с девятью рёбрами необходимо девять цветов. Его степень равна шести и его кратность равна трём.

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

Версия теоремы Визинга утверждает, что любой мультиграф с максимальной степенью $\Delta$ и кратностью $\mu$ можно раскрасить используя не более $\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)