Переполненный граф

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

$|E|>\mathrm{\Delta <!--\; \Delta \; -->}(G)\lfloor <!--\; \lfloor \; -->|V|/2\rfloor <!--\; \rfloor \; -->$$|E|>\Delta (G)\lfloor |V|/2\rfloor$.

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

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

СвойстваПравить

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

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

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

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

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

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

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

Гипотеза о переполненииПравить

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

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

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

АлгоритмыПравить

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

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

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