Мультиграф Шеннона
-
Мультиграфы Шеннона
- Названы Визингом в честь Клода Шеннона
- Используются в раскраске ребер
- Три вершины соединены одинаковым количеством ребер
-
Определение мультиграфа Шеннона
- Три вершины соединены ⌊n/2⌋, ⌊n/2⌋ и ⌊n+1/2⌋ ребрами соответственно
- Максимальная степень равна n
- Кратность равна ⌊n+1/2⌋
-
Примеры мультиграфов Шеннона
- Sh(2), Sh(3), Sh(4), Sh(5), Sh(6), Sh(7)
-
Теорема Шеннона
- Каждый мультиграф с максимальной степенью Δ имеет окраску краев, использующую не более 3/2Δ цветов
- Для четных Δ граница является жесткой
-
Теорема Визинга
- Каждый мультиграф с максимальной степенью Δ и множественностью μ может быть окрашен с использованием не более Δ+μ цветов
- Граница является жесткой для мультиграфов Шеннона