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

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

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

• a) все три вершины соединены одним и тем же числом рёбер.
• b) так же, как в a) но добавлено ещё одно дополнительное ребро.

Говоря точнее, граф является мультиграфом Шеннона ${\displaystyle 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 n}$. Его кратность (максимальное число рёбер, имеющих те же самые концы) равна ${\displaystyle \left\lfloor {\frac {n+1}{2}}\right\rfloor }$.