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

В теории графов мультиграфами Шеннона называется специальный вид треугольных графов, которые используются при исследовании рёберной раскраски. Визинг назвал эти графы в честь Клода Шеннона^[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 }$ цветов. Снова, эта граница точна для мультиграфов Шеннона.