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

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

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

• а) все три вершины соединены одинаковым количеством ребер.
• б) как в а) и добавляется одно дополнительное ребро.

Точнее, говорят о мультиграфе Шеннона 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$.

Примеры

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

Окраска края

Этот мультиграф Шеннона с девятью ребрами требует девяти цветов в любой раскраске ребер; степень его вершины равна шести, а кратность равна трем.

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

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

Ссылки

• Фиорини, С.; Уилсон, Робин Джеймс (1977), Раскраска ребер графов , Исследовательские заметки по математике, том. 16, Лондон: Питман, с. 34, ISBN  0-273-01129-4 , МР   0543798
• Шеннон, Клод Э. (1949), «Теорема о раскраске линий сети», J. Math. Физика , 28 : 148–151, doi : 10.1002/sapm1949281148 , hdl : 10338.dmlcz/101098 , MR   0030203 .
• Фолькманн, Лутц (1996), Основы теории графов (на немецком языке), Вена: Springer, стр. 289, ISBN  3-211-82774-9 .
• Визинг, В. Г. (1964), "Об оценке хроматического класса p -графа", Дискрет. Анализ. , 3 : 25–30, МР   0180505 .
• Визинг, В.Г. (1965), "Хроматический класс мультиграфа", Кибернетика , 1965 (3): 29–39, МР   0189915 .

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

• Лутц Фолькманн: Графики на каждом углу и на каждом краю . Конспект лекций 2006, с. 242 (английский)