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

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

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

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

Примеры

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

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

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

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

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

Примечания

В. Г. Визинг. Об оценке хроматического класса р-графа // сб. Дискретный анализ. — 1964. — Т. 3. — С. 25—30.
Claude E. Shannon. A theorem on coloring the lines of a network // J. Math. Physics. — 1949. — Т. 28. — С. 148—151.
В. Г. Визинг. Хроматический класс мультиграфа // Кибернетика. — 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: Graphen an allen Ecken und Kanten. Lecture notes 2006, p. 242 (German)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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