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

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

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

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

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

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

Ссылки

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

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

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