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

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

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

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

Примеры

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

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

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

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

Примечания

  1. В. Г. Визинг. Об оценке хроматического класса р-графа // сб. Дискретный анализ. — 1964. — Т. 3. — С. 25—30.
  2. Claude E. Shannon. A theorem on coloring the lines of a network // J. Math. Physics. — 1949. — Т. 28. — С. 148—151.
  3. В. Г. Визинг. Хроматический класс мультиграфа // Кибернетика. — 1965. — Вып. 3. — С. 29—39.

Литература

  • S. Fiorini, R. J. Wilson. Edge-colourings of graphs. — London: Pitman, 1977. — Т. 16. — С. 34. — (Research Notes in Mathematics). — ISBN 0-273-01129-4 .
  • Lutz Volkmann. Fundamente der Graphentheorie (неопр.) . — Wien: Springer, 1996. — С. 289. — ISBN 3-211-82774-9 .

Ссылки

  • Lutz Volkmann: . Lecture notes 2006, p. 242 (German)
Источник —

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