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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Мультиграфы Шеннона — это мультиграфы с тремя вершинами, для которых выполняется одно из следующих условий:
  • 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 .

Примеры[править | править вики-текст]

Рёберная раскраска[править | править вики-текст]

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

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

Версия теоремы Визинга (Vizing 1964) утверждает, что любой мультиграф с максимальной степенью \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.
  • Claude E. Shannon A theorem on coloring the lines of a network // J. Math. Physics. — 1949. — Т. 28. — С. 148–151..
  • Lutz Volkmann Fundamente der Graphentheorie. — Wien: Springer, 1996. — С. 289. — ISBN 3-211-82774-9..
  • В. Г. Визинг Об оценке хроматического класса р-графа // сб. Дискретный анализ. — 1964. — Т. 3. — С. 25–30..
  • В. Г. Визинг Хроматический класс мультиграфа // Кибернетика. — 1965. — В. 3. — С. 29–39..

Внешние ссылки[править | править вики-текст]