Переполненный граф ( англ. overfull graph ) — это такой простой граф ${\displaystyle G}$ (без кратных ребер и петель), размер которого ${\displaystyle |E|}$ больше произведения максимальной степени его вершин ${\displaystyle \displaystyle \Delta (G)}$ на округлённую вниз половину его порядка ${\displaystyle |V|}$

${\displaystyle |E|>\Delta (G)\lfloor |V|/2\rfloor }$ .

Если граф ${\displaystyle G}$ имеет переполненный подграф ${\displaystyle S}$ и ${\displaystyle \displaystyle \Delta (S)}$ = ${\displaystyle \displaystyle \Delta (G)}$ то ${\displaystyle G}$ - называется графом с переполненным подграфом ( англ. subgraph-overfull graph ) .

Понятие переполненный граф было введено при рассмотрении задач о раскраске ребер графа, а именно при решении вопроса о принадлежности графа к Классу 1 или Классу 2. Как следует из Теоремы Визинга, хроматический индекс графа может быть либо ${\displaystyle \chi ^{\prime }(G)=\Delta (G)}$ , и тогда граф принадлежит к Классу 1, либо ${\displaystyle \chi ^{\prime }(G)=\Delta (G)+1}$ и тогда граф принадлежит к Классу 2.

Свойства

Некоторые свойства переполненных графов:

• Из теоремы , которая гласит, что если граф ${\displaystyle G}$ обладает размером ${\displaystyle |E|}$ , таким что ${\displaystyle |E|>\beta _{1}(G)\Delta (G)}$ , где ${\displaystyle \beta _{1}(G)}$ есть реберное число независимости, а ${\displaystyle \Delta (G)}$ есть максимальная степень его вершин , то граф ${\displaystyle G}$ принадлежит Классу 2, и условия, что если граф порядка ${\displaystyle |V|}$ , то его реберное число независимости ${\displaystyle \beta _{1}(G)=\lfloor |V|/2\rfloor }$ , вытекает свойство:

Переполненный граф является графом Класса 2

• Доказывается как теорема :

Если у графа есть переполненный подграф, то сам граф - переполненный

• Доказывается как теорема .

Порядок переполненного графа - нечётное число

Гипотеза о переполнении

Четуинд и Хилтон в 1986 г. выдвинули гипотезу, известную сейчас как гипотеза о переполнении ( англ. Overfull Graph Conjecture )

Если для максимальной степени вершин графа выполняется условие ${\displaystyle 3\Delta (G)\geqslant |V|}$ , где ${\displaystyle |V|}$ есть порядок графа, то граф ${\displaystyle G}$ принадлежит к Классу 2 тогда и только тогда, когда он является графом с переполненным подграфом.

Эта гипотеза, если верна, имела бы многочисленные приложения к теории графов, включая гипотезу об 1-факторизации .

Алгоритмы

В работе приводится алгоритм, которые позволяет найти для графа ${\displaystyle G}$ у которого ${\displaystyle |V(S)|>|V(G)|-\Delta (G)}$ все порожденные переполненные подграфы ${\displaystyle S}$ за время ${\displaystyle O(n\log(n)+m)}$ , где ${\displaystyle n=|V(G)|}$ и ${\displaystyle m=|E(G)|}$ .

Вариант этого алгоритма позволяет для графа ${\displaystyle G}$ , у которого ${\displaystyle 2\Delta (G)\geq |V(G)|}$ найти все порожденные переполненные подграфы за линейное время ${\displaystyle O(n+m)}$ .

Также в работе приводится второй алгоритм, работающий с использованием первого алгоритма, который позволяет найти все порожденные переполненные подграфы графа ${\displaystyle G}$ , у которого ${\displaystyle 3\Delta (G)\geq |V(G)|}$ в общем случае за полиномиальное время ${\displaystyle O(n^{5/3}m)}$ , а для регулярного графа ${\displaystyle G}$ за время ${\displaystyle O(n^{3})}$ .

Примечания

Литература