Nedostatek (teorie grafů) - Deficiency (graph theory)

Nedostatek je koncept v teorie grafů který se používá k upřesnění různých vět vztahujících se k perfektní shoda v grafech, jako např Hallova věta o manželství. Is byl poprvé studován Øystein Ore.^[1][2]:17 Související vlastnost je přebytek.

Definice nedostatku

Nechat G = (PROTI, E) být graf, a nechť U být nezávislá sada vrcholů - podmnožina PROTI ve kterém žádné dva vrcholy nejsou spojeny hranou. Označit podle N_G(U) soubor sousedů U - podmnožina V, která obsahuje všechny vrcholy, které jsou spojeny hranou s jedním nebo více vrcholy U. The nedostatek sady U je definováno:

def_G(U) := |U| - | N_G(U)|

Předpokládat G je bipartitní graf, s biparticí PROTI = X u Y. nedostatek z G s ohledem na jednu z jeho částí (řekněme X), je maximální nedostatek podmnožiny X:

def (G;X): = max [U podmnožina X] def_G(U)

Někdy se toto množství nazývá kritický rozdíl G.^[3]

Všimněte si, že def_G prázdné podmnožiny je 0, takže def (G;X) ≥ 0.

Nedostatek a shoda

Pokud def (G;X) = 0, to znamená, že pro všechny podmnožiny U z X, | N_G(U)| ≥ |U|. Proto tím, že Hallova věta o manželství, G připouští a perfektní shoda.

Naproti tomu pokud def (G;X)> 0, to znamená, že u některých podmnožin U z X, | N_G(U)| < |U|. Stejnou větou tedy G nepřipouští a perfektní shoda. Navíc s využitím pojmu nedostatek je možné uvést kvantitativní verzi Hallova věty:

Každý bipartitní graf G = (X + Y, E) připouští shodu, ve které jsou maximálně def (G; X) vrcholy X neporovnatelné.

Důkaz. Nechat d = def (G; X). To znamená, že pro každou podskupinu U z X, | N_G(U)| ≥ |U|-d. Přidat d fiktivní vrcholy do Ya připojte každý fiktivní vrchol ke všem vrcholům X. Po přidání pro každou podmnožinu U z X, | N_G(U)| ≥ |U|. Podle Hallovy věty o manželství nový graf připouští shodu, ve které všechny vrcholy X jsou uzavřeny. Nyní obnovte původní graf odstraněním d fiktivní vrcholy; to ponechává nanejvýš d vrcholy X bezkonkurenční. Jiné způsoby, jak vyjádřit tuto větu, jsou:^[2]:17

${ displaystyle nu (G) = | X | - operatorname {def} (G; X)}$

kde ν(G) je velikost maximální shody v G (nazývané také odpovídající číslo G).

Vlastnosti funkce nedostatku

V bipartitní graf G = (X+Y, E), funkce nedostatku je a funkce supermodulární sady: pro každé dvě podmnožiny X₁, X₂ z X:^{[2]:Lem. 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})}$

A těsný podmnožina je podmnožinou X jehož nedostatek se rovná nedostatku celého grafu (tj. rovná se maximu). Průsečík a spojení těsných sad je těsné; vyplývá to z vlastností funkcí supermodulární množiny s horním ohraničením.^{[2]:Lem. 1.3.3}

V nebipartitním grafu není funkce deficitu obecně supermodulární.

Silná vlastnost Hall

Graf G má Hallův majetek pokud pro tento graf platí Hallova věta o manželství, konkrétně pokud G má buď dokonalou shodu, nebo vrchol s kladným nedostatkem. Graf má silná vlastnost Hall pokud def (G) = | V | - 2 ν (G). Je zřejmé, že silná vlastnost Hall znamená vlastnost Hall. Bipartitní grafy mají obě tyto vlastnosti, existují však třídy nebipartitních grafů, které mají tyto vlastnosti.

Zejména graf má silnou Hallovu vlastnost, pokud a pouze - pokud je stabilní - jeho maximální velikost shody se rovná jeho maximálnímu zlomková shoda velikost.^[3]

Přebytek

The přebytek podmnožiny U z PROTI je definováno:

sur_G(U): = | N_G(U)| - |U| = - def_G(U)

Přebytek grafu G w.r.t. podmnožina X je definován minimálním přebytkem neprázdný podmnožiny X:^[2]:19

sur (G;X): = min [U neprázdná podmnožina X] sur_G(U)

Všimněte si omezení na neprázdné podmnožiny: bez něj by přebytek všech grafů byl vždy 0. Všimněte si také, že:

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

V bipartitním grafu G = (X+Y, E), funkce přebytku je a funkce submodulární sady: pro každé dvě podmnožiny X₁, X₂ z X:

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

A těsný podmnožina je podmnožinou X jehož přebytek se rovná přebytku celého grafu (tj. rovná se minimálnímu). Křižovatka a spojení těsných množin s neprázdnou křižovatkou jsou těsné; vyplývá to z vlastností funkcí submodulární množiny se sníženou hranicí.^{[2]:Lem. 1.3.5}

Pro bipartitní graf G s def (G;X) = 0, číslo sur (G;X) je největší celé číslo s splňující následující vlastnost pro každý vrchol X v X: pokud přidáme s nové vrcholy do X a připojte je k vrcholům v N_G(X), výsledný graf má nezáporný přebytek.^{[2]:Thm. 1.3.6}

Li G je bipartitní graf s kladným přebytkem, který vylučuje jakoukoli hranu G snižuje sur (G;X), pak každý vrchol dovnitř X má titul sur (G;X) +1.^[4]

Bipartitní graf má kladný přebytek (w.r.t. X) pokud a pouze - pokud obsahuje les F tak, že každý vrchol v X má titul 2 v F.^{[2]:Thm. 1.3.8}

Grafy s kladným přebytkem hrají důležitou roli v teorii grafových struktur; viz Gallai – Edmondsův rozklad.

V nebipartitním grafu není funkce přebytku obecně submodulární.

Reference