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

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

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

Мультиграфы Шеннона — это мультиграфы с тремя вершинами, для которых выполняется одно из следующих условий:
  • a) все три вершины соединены одним и тем же числом рёбер.
  • b) так же, как в a) но добавлено ещё одно дополнительное ребро.

Говоря точнее, граф является мультиграфом Шеннона , если три вершины соединены , и рёбрами соответственно. Этот мультиграф имеет максимальную степень . Его кратность (максимальное число рёбер, имеющих те же самые концы) равна .

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

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

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

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

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

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

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

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