Дефицит (теория графов) - 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

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

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

В двудольный граф грамм = (Икс+Y, E) дефектная функция есть функция супермодульного набора: для каждых двух подмножеств Икс1, Икс2 из Икс:[2]:Лем.1.3.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) прибавочная функция - это функция субмодульного набора: для каждых двух подмножеств Икс1, Икс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

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

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

Рекомендации

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