Дефицит (теория графов)

Дефицит — это концепция в теории графов , которая используется для уточнения различных теорем, связанных с идеальным соответствием в графах, таких как теорема Холла о браке . Впервые это изучил Эйстейн Оре . ^[1]^[2]^: 17 Соответствующее имущество является избыточным .

Определение дефицита

Пусть $G = (V, E)$ — граф, и пусть U — независимый набор вершин, то есть U — подмножество V , в котором никакие две вершины не соединены ребром. Пусть $NG, которое образовано всеми вершинами из 'V' , (U)$ обозначает множество соседей U которые соединены ребром с одной или несколькими вершинами U' . Дефицит определяется множества U следующим образом:

\mathrm {def} _{G}(U):=|U|-|N_{G}(U)|

Предположим, что — двудольный граф с двудольным разделением V = X ∪ Y. G Недостаток — G X по отношению к одной из его частей (скажем, ) это максимальный недостаток подмножества X :

\mathrm {def} (G;X):=\max _{U\subseteq X}\mathrm {def} _{G}(U)

называют критической разностью G. эту величину Иногда ^[3]

Обратите внимание, что def _G пустого подмножества равен 0, поэтому def( G; X) ≥ 0.

Дефицит и совпадения

Если def( G; X) = 0, это означает, что для всех подмножеств U из X |N _G ( U )| ≥ | У |. Следовательно, по Холла о браке теореме G допускает совершенное паросочетание .

Напротив, если def( G; X) > 0, это означает, что для некоторых подмножеств U из X |N _G ( U )| < | У |. Следовательно, по той же теореме G не допускает совершенного паросочетания . Более того, используя понятие дефицита, можно сформулировать количественную версию теоремы Холла:

Теорема . Каждый двудольный граф G = ( X + Y , E ) допускает паросочетание, в котором не более def( G ; X ) вершин X не совпадают.

Доказательство . Пусть d = def(G;X). Это означает, что для любого подмножества U из X |N _G ( U )| ≥ | У |- д . Добавьте d фиктивных вершин в Y и соедините каждую фиктивную вершину со всеми X. вершинами После сложения для каждого подмножества U из X |N _G ( U )| ≥ | У |. По теореме о браке Холла новый граф допускает паросочетание, в котором все вершины X. совпадают Теперь восстановите исходный граф, удалив d фиктивных вершин; не более d вершин X. это оставляет непревзойденными

Эту теорему можно эквивалентно сформулировать так: ^[2]^: 17

\nu (G)=|X|-\operatorname {def} (G;X),

где ν ( G размер максимального паросочетания в G (называемого числом паросочетания G ) — ).

Свойства функции дефицита

В двудольном графе G = ( X + Y , E ) функция дефицита является супермодульной функцией множества : для каждых двух подмножеств X ₁ , X ₂ из X : ^[2]^{: Лем.1.3.2}

$\operatorname {def} _{G}(X_{1}\cup X_{2})+\operatorname {def} _{G}(X_{1}\cap X_{2})\geq \operatorname {def} _{G}(X_{1})+\operatorname {def} _{G}(X_{2})$

подмножество Плотное — это подмножество X , дефицит которого равен дефициту всего графа (т. е. равен максимуму). Пересечение и объединение тесных множеств являются плотными; это следует из свойств ограниченных сверху супермодулярных функций множества. ^[2]^{: Лем.1.3.3}

В недвудольном графе функция дефекта, вообще говоря, не является супермодулярной.

Собственность Сильного зала

Граф G обладает свойством Холла , если для этого графа справедлива теорема Холла о браке, а именно, если G имеет либо идеальное паросочетание, либо множество вершин с положительным дефектом. Граф обладает сильным свойством Холла , если def(G) = |V| - 2 ν(G). Очевидно, из сильного холловского свойства следует холловское свойство. Двудольные графы обладают обоими этими свойствами, однако существуют классы недвудольных графов, обладающих этими свойствами.

В частности, граф обладает сильным свойством Холла тогда и только тогда, когда он стабилен - его максимальный размер соответствия равен максимальному размеру дробного соответствия . ^[3]

Избыток

Избыток подмножества U V из : определяется следующим образом

на _G ( U ) := |N _G ( U )| − | У | −def _G ( U =

Избыток графа G относительно подмножества X определяется минимальным избытком непустых подмножеств X : ^[2]^: 19

sur( G; X) := min [ U непустое подмножество X ] sur _G ( U )

Обратите внимание на ограничение на непустые подмножества: без него избыток всех графов всегда был бы равен 0. Также обратите внимание на то, что:

def(G;X) = max[0, −sur( G; X)]

В двудольном графе G = ( X + Y , E ) избыточная функция является субмодулярной функцией множества : для каждых двух подмножеств X ₁ , X ₂ из X :

$\operatorname {sur} _{G}(X_{1}\cup X_{2})+\operatorname {sur} _{G}(X_{1}\cap X_{2})\leq \operatorname {sur} _{G}(X_{1})+\operatorname {sur} _{G}(X_{2})$

Подмножество , ограниченное по избытку, — это подмножество X , излишек которого равен излишку всего графа (т. е. равен минимуму). Пересечение и объединение плотных множеств с непустым пересечением являются тесными; это следует из свойств субмодулярных функций множества, ограниченных снизу. ^[2]^{: Лем.1.3.5}

Для двудольного графа G с def( G ; X ) = 0 число sur( G ;X) — это наибольшее целое число s, удовлетворяющее следующему свойству для каждой вершины x в X : если мы добавим s новых вершин в X и соединим их к вершинам из NG ₍ ) x , полученный граф имеет неотрицательный избыток. ^[2]^{: Thm.1.3.6}

Если G — двудольный граф с положительным избытком, такой, что удаление любого ребра из G уменьшает sur( G; X), то каждая вершина в X имеет степень sur( G ;X) + 1. ^[4]

Двудольный граф имеет положительный излишек (относительно X ) тогда и только тогда, когда он содержит лес такой , что каждая вершина в X имеет степень 2 в F. F ^[2]^{: Thm.1.3.8}

Графы с положительным избытком играют важную роль в теории графовых структур; см. разложение Галлаи – Эдмондса .

В недвудольном графе прибавочная функция, вообще говоря, не является субмодулярной.

Ссылки

^ Оре, Эйстейн (1 декабря 1955 г.). «Графы и теоремы соответствия» . Математический журнал Дьюка . 22 (4): 625–639. дои : 10.1215/S0012-7094-55-02268-7 . ISSN 0012-7094 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Ловас, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1 МР 0859549
^ Jump up to: ^а ^б Беккенбах, Изабель; Борндорфер, Ральф (01 октября 2018 г.). «Теорема Холла и Кенига в графах и гиперграфах». Дискретная математика . 341 (10): 2753–2761. дои : 10.1016/j.disc.2018.06.013 . ISSN 0012-365X .
^ Ловас, Л. (1 сентября 1970 г.). «Обобщение теоремы Кенига». Математический журнал Венгерской академии наук . 21 (3): 443–446. дои : 10.1007/BF01894789 . ISSN 1588-2632 . S2CID 121333106 .

[1] Оре, Эйстейн (1 декабря 1955 г.). «Графы и теоремы соответствия» . Математический журнал Дьюка . 22 (4): 625–639. дои : 10.1215/S0012-7094-55-02268-7 . ISSN 0012-7094 .

[lp-2] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Ловас, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1 МР 0859549

[:0-3] Jump up to: ^а ^б Беккенбах, Изабель; Борндорфер, Ральф (01 октября 2018 г.). «Теорема Холла и Кенига в графах и гиперграфах». Дискретная математика . 341 (10): 2753–2761. дои : 10.1016/j.disc.2018.06.013 . ISSN 0012-365X .

[4] Ловас, Л. (1 сентября 1970 г.). «Обобщение теоремы Кенига». Математический журнал Венгерской академии наук . 21 (3): 443–446. дои : 10.1007/BF01894789 . ISSN 1588-2632 . S2CID 121333106 .

[1]

[2]

[3]

[4]