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

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

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

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

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

Примеры

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

Рёберная раскраска

Для рёберной раскраски мультиграфа Шеннона с девятью рёбрами необходимо девять цветов. Его степень равна шести и его кратность равна трём.

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

Версия теоремы Визинга^[3] утверждает, что любой мультиграф с максимальной степенью $\Delta$ и кратностью $\mu$ можно раскрасить используя не более $\Delta +\mu$ цветов. Снова, эта граница точна для мультиграфов Шеннона.

Примечания

↑ В. Г. Визинг. Об оценке хроматического класса р-графа // сб. Дискретный анализ. — 1964. — Т. 3. — С. 25—30.
↑ Claude E. Shannon. A theorem on coloring the lines of a network // J. Math. Physics. — 1949. — Т. 28. — С. 148—151.
↑ В. Г. Визинг. Хроматический класс мультиграфа // Кибернетика. — 1965. — Вып. 3. — С. 29—39.

Литература

S. Fiorini, R. J. Wilson. Edge-colourings of graphs. — London: Pitman, 1977. — Т. 16. — С. 34. — (Research Notes in Mathematics). — ISBN 0-273-01129-4.
Lutz Volkmann. Fundamente der Graphentheorie (неопр.). — Wien: Springer, 1996. — С. 289. — ISBN 3-211-82774-9.

Ссылки

Lutz Volkmann: Graphen an allen Ecken und Kanten. Lecture notes 2006, p. 242 (German)

Похожие исследовательские статьи

Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:

как и геометрия, обладает наглядностью;
как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
не имеет громоздкого математического аппарата ;
имеет выраженный прикладной характер.

Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.

Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.

По́лный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна. Полный граф с $\text{[math]}$ вершинами имеет $\text{[math]}$ рёбер и обозначается $\text{[math]}$ . Является регулярным графом степени $\text{[math]}$ .

Хромати́ческое число графа — минимальное число цветов, в которые можно раскрасить вершины графа так, чтобы концы любого ребра имели разные цвета.

Рёберная раскраска — назначение «цветов» рёбрам графа таким образом, что никакие два смежных ребра не имеют один и тот же цвет. Рёберная раскраска — это один из видов различных типов раскраски графов. Задача рёберной раскраски задаётся вопросом, можно ли раскрасить рёбра заданного графа максимум в $\text{[math]}$ различных цветов для заданного значения $\text{[math]}$ или для минимального возможного числа цветов. Минимальное требуемое число цветов для раскраски рёбер заданного графа называется хроматическим индексом графа. Например, рёбра графа на иллюстрации можно раскрасить в три цвета, но нельзя раскрасить в два, так что граф имеет хроматический индекс 3.

В теории графов тотальной раскраской называется вид раскраски вершин и рёбер графа. Если не указано явно другое, тотальная раскраска предполагается правильной в том смысле, что никакие смежные вершины и никакие смежные рёбра и вершины, лежащие на концах рёбер, не раскрашиваются в один и тот же цвет.

Теорема Визинга — утверждение теории графов, согласно которому рёбра любого простого неориентированного графа могут быть раскрашены в число цветов, максимум на единицу большее максимальной степени вершин $\text{[math]}$ графа. Поскольку $\text{[math]}$ цветов достаточно всегда, все неориентированные графы можно разбить на два класса — графы «первого класса», для которых $\text{[math]}$ цветов достаточно, и «второго класса», для которых необходимо $\text{[math]}$ цветов.

Граф Турана T(n,r) — это граф, образованный разложением n вершин на r подмножеств, с как можно близким размером, и вершины в этом графе соединены ребром, если они принадлежат разным подмножествам. Граф будет иметь $\text{[math]}$ подмножеств размером $\text{[math]}$ и $\text{[math]}$ подмножеств размером $\text{[math]}$ . Таким образом, это полный r-дольный граф

\text{[math]}

Кнезеровский граф $\text{[math]}$ — это неориентированный граф, описывающий отношение непересекаемости $\text{[math]}$ -элементных подмножеств $\text{[math]}$ -элементного множества друг с другом.

В теории графов число пересечений cr(G) графа G — это наименьшее число пересечений рёбер плоского рисунка графа G. Например, граф является планарным тогда и только тогда, когда его число пересечений равно нулю.

В теории графов доматическое разбиение графа $\text{[math]}$ — это разбиение множества вершин $\text{[math]}$ на непересекающиеся множества $\text{[math]}$ , $\text{[math]}$ ,..., $\text{[math]}$ , такие, что каждое множество V_i является доминирующим множеством графа G. Рисунок справа показывает доматическое разбиение графа. На рисунке доминирующее множество $\text{[math]}$ состоит из жёлтых вершин, $\text{[math]}$ состоит из зелёных вершин, а $\text{[math]}$ состоит из синих вершин.

Экстремальная теория графов — это ветвь теории графов. Экстремальная теория графов изучает экстремальные свойства графов, удовлетворяющих определённым условиям. Экстремальность может относиться к различным инвариантам графов, таким как порядок, размер или обхват. В более абстрактном смысле теория изучает, как глобальные свойства графа влияют на локальные подструктуры графа.

Степень k неориентированного графа G — это другой граф, имеющий тот же самый набор вершин, и две вершины этого графа смежны, если расстояние между этими вершинами в исходном графе G не превышает k. Для указания степени графа используется терминология, аналогичная степеням чисел — G² называется квадратом графа G, G³ называется кубом.

Гипотеза Албертсона — недоказанная связь между числом пересечением и хроматическим числом графа. Гипотеза носит имя Михаила О. Албертсона, профессора колледжа Смит, который сформулировал утверждение в качестве гипотезы в 2007. Гипотеза является одной из многих гипотез в теории раскраски графов. Гипотеза утверждает, что среди всех графов, требующих n цветов, полный граф K_n находится среди графов, имеющих наименьшее число пересечений. Эквивалентно, если граф может быть нарисован с меньшим числом пересечений, чем у K_n, тогда, согласно гипотезе, его можно раскрасить в меньше чем n цветов.

Линейный лес — это вид леса, образованного из дизъюнктного объединения путей. Это ориентированный граф, не имеющий циклов, в котором каждая вершина имеет степень, не превосходящую трёх. Линейные леса — это то же самое, что и леса без клешенй. Это также графы, инвариант Колен де Вердьера которых не превосходит 1.

Алгоритм раскраски рёбер Мисры и Гриса — это алгоритм полиномиального времени в теории графов, который находит рёберную раскраску любого графа. Раскраска требует максимум $\text{[math]}$ цветов, где $\text{[math]}$ — максимальная степень графа. Это значение оптимально для некоторых графов, а по теореме Визинга оно на один цвет больше, чем оптимальная раскраска остальных графов.

Переполненный граф — это такой простой граф $\text{[math]}$ , размер которого $\text{[math]}$ больше произведения максимальной степени его вершин $\text{[math]}$ на округлённую вниз половину его порядка $\text{[math]}$

\text{[math]}

<span class="mw-page-title-main">Теорема Мендельсона — Далмейджа</span>

Теорема Мендельсона — Далмейджа — утверждение о свойстве паросочетаний в двудольных графах: если для двудольного графа $\text{[math]}$ с подмножествами вершин $\text{[math]}$ и $\text{[math]}$ существуют паросочетания $\text{[math]}$ и $\text{[math]}$ такие, что $\text{[math]}$ насыщает $\text{[math]}$ , а $\text{[math]}$ насыщает $\text{[math]}$ , то существует паросочетание $\text{[math]}$ , которое насыщает одновременно множества $\text{[math]}$ и $\text{[math]}$

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

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.