Мультиграф Шеннона - Shannon multigraph - Wikipedia

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

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

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

Точнее говорят о мультиграфе Шеннона. Ш (п), если три вершины соединены ${\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 \left\lfloor {\frac {n+1}{2}}\right\rfloor }$.

Примеры

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

  Ш (2)

• 

  Ш (3)

• 

  Ш (4)

• 

  Ш (5)

• 

  Ш (6)

• 

  Ш (7)

Краска окраски

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

Согласно теореме Шеннон (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 }$ цвета в любой правильной окраске края.

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

Рекомендации

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

внешняя ссылка

• Лутц Фолькманн: Graphen an allen Ecken und Kanten. Конспект лекций 2006 г., стр. 242 (немецкий)