Tvrdost grafu - Graph toughness

V tomto grafu by odstranění čtyř červených vrcholů vytvořilo čtyři připojené komponenty (zobrazené ve čtyřech různých barvách). Neexistuje však žádná sada k vrcholy, jejichž odstranění zanechává více než k komponenty. Proto je jeho houževnatost přesně 1.

v teorie grafů, houževnatost je měřítkem připojení grafu. Graf G se říká, že je t-tak za dané reálné číslo t pokud pro každého celé číslo k > 1, G nelze rozdělit na k odlišný připojené komponenty odstraněním méně než tk vrcholy. Například graf je 1- těžké, pokud je počet komponent vytvořených odstraněním sady vrcholů vždy maximálně stejně velký jako počet odstraněných vrcholů. Tvrdost grafu je maximální t pro které to je t-tvrdý; toto je konečné číslo pro všechny konečné grafy kromě kompletní grafy, které podle konvence mají nekonečnou houževnatost.

Tvrdost grafu poprvé představil Václav Chvátal  (1973 ). Od té doby se mnoho matematiků zabývalo houževnatostí; nedávný průzkum od Bauer, Broersma & Schmeichel (2006) uvádí 99 vět a 162 prací na toto téma.

Příklady

Odstraňování k vrcholy z a graf cesty může rozdělit zbývající graf na tolik k + 1 připojené komponenty. Maximální poměr komponent k odstraněným vrcholům je dosažen odstraněním jednoho vrcholu (z vnitřku cesty) a jeho rozdělením na dvě komponenty. Cesty proto jsou 1/2- těžké. Naproti tomu odstranění k vrcholy z a graf cyklu listy nanejvýš k zbývající připojené součásti a někdy přesně odejde k připojené komponenty, takže cyklus je 1- těžké.

Připojení k vrcholné konektivitě

Pokud je graf t-tvrdý, pak jeden důsledek (získaný nastavením k = 2) je libovolná sada 2t − 1 uzly lze odebrat bez rozdělení grafu na dvě části. To je každý t-tvrdý graf je také 2t-vertex-connected.

Spojení s Hamiltonicity

Nevyřešený problém v matematice: Existuje číslo ${displaystyle t}$ takové, že každý ${displaystyle t}$-tvrdý graf je Hamiltonian? (více nevyřešených úloh z matematiky)

Chvátal (1973) poznamenal, že každý cyklus, a tedy každý Hamiltonovský graf, je 1-tvrdý; to znamená být 1-tvrdý je nutná podmínka aby byl graf hamiltonovský. Domníval se, že spojení mezi houževnatostí a Hamiltonicitou jde oběma směry: že existuje prahová hodnota t takové, že každý t-tough graph is Hamiltonian. Chvátalova původní domněnka, že t = 2 by se ukázalo Fleischnerova věta ale byl vyvrácen Bauer, Broersma & Veldman (2000). Existence většího prahu houževnatosti pro Hamiltonicity zůstává otevřená a někdy se jí říká Chvátalova domněnka tvrdosti.

Výpočetní složitost

Testování, zda je graf 1-tak je co-NP -kompletní. Toto je rozhodovací problém jehož odpověď je „ano“ pro graf, který není 1-tuhý, a „ne“ pro graf, který není 1-tuhý, je NP-kompletní. Totéž platí pro jakýkoli pevný klad racionální číslo q: testování, zda je graf q-tough is co-NP-complete (Bauer, Hakimi & Schmeichel 1990 ).

Viz také

• Síla grafu, analogický koncept pro odstranění hran
• Tutte-Bergeův vzorec, související charakterizace velikosti maximální shody v grafu

Reference

• Bauer, Douglas; Broersma, Hajo; Schmeichel, Edward (2006), „Houževnatost v grafech - průzkum“, Grafy a kombinatorika, 22 (1): 1–35, doi:10.1007 / s00373-006-0649-0, PAN  2221006, S2CID  3237188.
• Bauer, D .; Broersma, H. J .; Veldman, H. J. (2000), „Ne každý 2 tvrdý graf je hamiltoniánský“ Sborník 5. semináře Twente o grafech a kombinatorické optimalizaci (Enschede, 1997), Diskrétní aplikovaná matematika (1-3 ed.), 99 (1–3): 317–321, doi:10.1016 / S0166-218X (99) 00141-9, PAN  1743840.
• Bauer, D .; Hakimi, S.L.; Schmeichel, E. (1990), „Rozpoznávání náročných grafů je NP-tvrdé“, Diskrétní aplikovaná matematika, 28 (3): 191–195, doi:10.1016 / 0166-218X (90) 90001-S, PAN  1074858.
• Chvátal, Václav (1973), „Tvrdé grafy a hamiltonovské obvody“, Diskrétní matematika, 5 (3): 215–228, doi:10.1016 / 0012-365X (73) 90138-6, PAN  0316301.