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

Электромонтаж Ремонт и отделка Укладка напольных покрытий, теплые полы Тепловодоснабжение

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

10.09.2021

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

| E | > Δ ( G ) ⌊ | V | / 2 ⌋ {displaystyle |E|>Delta (G)lfloor |V|/2 floor } .

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

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

Свойства

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

  • Из теоремы, которая гласит, что если граф G {displaystyle G} обладает размером | E | {displaystyle |E|} , таким что | E | > β 1 ( G ) Δ ( G ) {displaystyle |E|>eta _{1}(G)Delta (G)} , где β 1 ( G ) {displaystyle eta _{1}(G)} есть реберное число независимости, а Δ ( G ) {displaystyle Delta (G)} есть максимальная степень его вершин , то граф G {displaystyle G} принадлежит Классу 2, и условия, что если граф порядка | V | {displaystyle |V|} , то его реберное число независимости β 1 ( G ) = ⌊ | V | / 2 ⌋ {displaystyle eta _{1}(G)=lfloor |V|/2 floor } , вытекает свойство:
Переполненный граф является графом Класса 2
  • Доказывается как теорема:
Если у графа есть переполненный подграф, то сам граф - переполненный
  • Доказывается как теорема.
Порядок переполненного графа - нечётное число

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

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

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

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

Алгоритмы

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

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

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


Имя:*
E-Mail:
Комментарий: