WikiSort.ru - Не сортированное

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

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

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

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

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

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

Внешние ссылки

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

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка.