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

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

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

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

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

Примеры

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

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

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

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

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

Литература

• Шаблон:Книга
• Шаблон:Книга

Ссылки

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