Дефицит (теория графов) - Deficiency (graph theory)

Дефицит это концепция в теория графов который используется для уточнения различных теорем, связанных с идеальное соответствие в графиках, например Теорема холла о браке. Впервые был изучен Øystein Ore.^[1]^[2]^:17 Связанное свойство избыток.

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

Позволять грамм = (V, E) - граф, и пусть U быть независимый набор вершин - подмножество V в котором никакие две вершины не соединены ребром. Обозначим через N_грамм(U) множество соседей U - подмножество V, которое содержит все вершины, которые соединены ребром с одной или несколькими вершинами U. В недостаток из набора U определяется:

def_грамм(U) := |U| - | N_грамм(U)|

Предполагать грамм это двудольный граф, с двудольным V = Икс u Y. недостаток из грамм по отношению к одной из его частей (скажем, Икс), является максимальным дефицитом подмножества Икс:

def (ГРАММ;X): = max [U подмножество Икс] def_грамм(U)

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

Обратите внимание, что def_грамм пустого подмножества равно 0, поэтому def (ГРАММ;Х) ≥ 0.

Недостаток и соответствие

Если def (ГРАММ;X) = 0, это означает, что для всех подмножеств U из Икс, | N_грамм(U)| ≥ |U|, Следовательно, по Теорема холла о браке, грамм признает идеальное соответствие.

Напротив, если def (ГРАММ;X)> 0, это означает, что для некоторых подмножеств U из Икс, | N_грамм(U)| < |U|, Следовательно, по той же теореме грамм не допускает идеальное соответствие. Более того, используя понятие дефекта, можно сформулировать количественную версию теоремы Холла:

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

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

${ Displaystyle Nu (G) = | Икс | - OperatorName {def} (G; X)}$

куда ν(G) размер максимального соответствия в G (также называемый совпадающий номер из G).

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

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

${ displaystyle 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})}$

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

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

Собственность Strong Hall

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

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

Избыток

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

сюр_грамм(U): = | N_грамм(U)| - |U| = - def_грамм(U)

Излишек графика грамм w.r.t. подмножество Икс определяется минимальным избытком непустой подмножества Икс:^[2]^:19

сюр (ГРАММ;X): = мин [U непустое подмножество Икс] сюр_грамм(U)

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

def (G; X) = max [0, - sur (ГРАММ; ИКС)]

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

${ displaystyle 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})}$

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

Для двудольного графа грамм с def (грамм;Икс) = 0, число sur (ГРАММ;X) - наибольшее целое число s удовлетворяющий следующему свойству для каждой вершины Икс в Икс: если мы добавим s новые вершины для Икс и соедините их с вершинами в N_грамм(Икс) полученный граф имеет неотрицательный излишек.^[2]^:Thm.1.3.6

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

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

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

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