Русская Википедия:Переполненный граф

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Переполненный граф (Шаблон:Lang-en) Шаблон:Sfn — это такой простой граф <math>G</math> (без кратных ребер и петель), размер которого <math>|E|</math> больше произведения максимальной степени его вершин <math>\displaystyle\Delta(G)</math> на округлённую вниз половину его порядка <math>|V|</math>

<math>|E| > \Delta (G) \lfloor |V|/2 \rfloor</math>.

Если граф <math>G</math> имеет переполненный подграф <math>S</math> и <math>\displaystyle\Delta(S)</math> = <math>\displaystyle\Delta(G)</math> то <math>G</math> - называется графом с переполненным подграфом (Шаблон:Lang-en)Шаблон:SfnШаблон:Sfn.

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

Свойства

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

• Из теоремыШаблон:Sfn, которая гласит, что если граф <math>G</math> обладает размером <math>|E|</math>, таким что <math>|E| > \beta_1(G) \Delta (G)</math>, где <math>\beta_1(G)</math> есть реберное число независимости, а <math> \Delta (G)</math> есть максимальная степень его вершин , то граф <math>G</math> принадлежит Классу 2, и условия, что если граф порядка <math>|V|</math>, то его реберное число независимости <math>\beta_1(G)=\lfloor |V|/2 \rfloor</math>, вытекает свойство:

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

• Доказывается как теоремаШаблон:Sfn:

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

• Доказывается как теоремаШаблон:Sfn.

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

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

Четуинд и Хилтон Шаблон:Sfn в 1986 г. выдвинули гипотезу, известную сейчас как гипотеза о переполнении (Шаблон:Lang-en)

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

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

Алгоритмы

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

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

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

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья (Research Paper 7)