Hadwigerovo číslo - Hadwiger number

v teorie grafů, Hadwigerovo číslo z neorientovaný graf G je velikost největšího kompletní graf které lze získat pomocí stahovací hrany z GRovněž číslo Hadwiger h(G) je největší číslo k pro který je kompletní graf K.k je Méně důležitý z G, menší graf získaný z G kontrakcemi hran a odstraněním vrcholů a hran. Číslo Hadwiger je také známé jako číslo kontrakční kliky z G[1] nebo stupeň homomorfismu z G.[2] Je pojmenován po Hugo Hadwiger, který jej představil v roce 1943 ve spojení s Hadwigerův dohad, kde se uvádí, že Hadwigerovo číslo je vždy minimálně stejně velké jako chromatické číslo zG.
Grafy, které mají Hadwigerův počet nejvýše čtyři, byly charakterizovány Wagner (1937). Grafy s jakoukoli konečnou vazbou na Hadwigerovo číslo jsou řídké a mají malé chromatické číslo. Určení Hadwigerova čísla grafu je NP-tvrdé ale fixovatelný parametr.
Grafy s malým počtem Hadwigerů
Graf G má Hadwigerovo číslo nanejvýš dvě právě tehdy, když je les, pro tři vrcholy může být úplný moll vytvořen pouze kontrakcí a cyklus vG.
Graf má Hadwigerovo číslo nejvýše tři právě tehdy, je-li jeho šířka stromu je nanejvýš dva, což je pravda právě tehdy, když každý z nich vzájemně propojené komponenty je sériově paralelní graf.

Wagnerova věta, který charakterizuje rovinné grafy od jejich zakázané nezletilé, znamená, že rovinné grafy mají Hadwigerovo číslo maximálně čtyři. Ve stejné práci, která dokázala tuto větu, Wagner (1937) také přesněji charakterizoval grafy s Hadwigerovým číslem nejvýše čtyři: jsou to grafy, které mohou být tvořeny klika-součet operace, které kombinují rovinné grafy s osmi vrcholy Wagnerův graf.
Grafy s číslem Hadwiger nejvýše pět zahrnují vrcholové grafy a bez vložení grafů, oba mají kompletní graf K.6 mezi jejich zakázanými nezletilými.[3]
Řídkost
Každý graf s n vrcholy a Hadwigerovo číslo k má O (nk √log k) hrany. Tato vazba je pevná: pro každého k, existují grafy s Hadwigerovým číslem k které mají Ω (nk √log k) hrany.[4] Pokud graf G má číslo Hadwiger k, pak všechny jeho podgrafy mají také nanejvýš Hadwigerovo číslo ka z toho vyplývá G musí mít zvrhlost Ó(k √log k). Proto jsou grafy s omezeným Hadwigerovým číslem řídké grafy.
Zbarvení
The Hadwigerův dohad uvádí, že Hadwigerovo číslo je vždy minimálně stejně velké jako chromatické číslo zG. To znamená, že každý graf s Hadwigerovým číslem k by měl mít zbarvení grafu maximálně k barvy. Pouzdro k = 4 je ekvivalentní (Wagnerovou charakteristikou grafů s tímto Hadwigerovým číslem) čtyřbarevná věta na barvení rovinné grafy a domněnka byla také prokázána k ≤ 5, ale zůstává neprokázáno pro větší hodnotyk.[5]
Kvůli jejich nízké degeneraci jsou grafy s Hadwigerovým číslem maximálně k lze obarvit a chamtivé zbarvení algoritmus používající O (k √log k) barvy.
Výpočetní složitost
Testování, zda je Hadwigerovo číslo daného grafu alespoň daná hodnota k je NP-kompletní,[6] z čehož vyplývá, že určení Hadwigerova čísla je NP-tvrdé. Problém však je fixovatelný parametr: existuje algoritmus pro nalezení největší menší kliky v čase, který závisí pouze polynomiálně na velikosti grafu, ale exponenciálně v h(G).[7] Kromě toho mohou polynomiální časové algoritmy aproximovat Hadwigerovo číslo výrazně přesněji než nejlepší aproximace polynomiálního času (za předpokladu P ≠ NP) na velikost největšího kompletní podgraf.[7]
Související pojmy
The achromatické číslo grafu G je velikost největší kliky, kterou lze vytvořit uzavřením smlouvy o rodině nezávislé sady v G.
Nespočet kliky nezletilých v nekonečných grafech lze charakterizovat z hlediska ráje, které jistě formalizují únikové strategie pronásledování hry: pokud je Hadwigerovo číslo nepočítatelné, pak se rovná největšímu řádu útočiště v grafu.[8]
Každý graf s Hadwigerovým číslem k má nanejvýš n2Ó(k log logk) kliky (kompletní podgrafy).[9]
Halin (1976) definuje třídu parametrů grafu, které volá S-funkce, které zahrnují Hadwigerovo číslo. Tyto funkce od grafů po celá čísla musí být nulové grafy bez hran, být menší monotónní,[10] zvýšit o jeden, když je přidán nový vrchol sousedící se všemi předchozími vrcholy, a získat větší hodnotu ze dvou podgrafů na obou stranách klika oddělovač. Sada všech těchto funkcí tvoří a úplná mříž v rámci operací elementární minimalizace a maximalizace. Spodní prvek v této mřížce je Hadwigerovo číslo a horní prvek je šířka stromu.
Poznámky
- ^ Bollobás, Catlin & Erdős (1980).
- ^ Halin (1976).
- ^ Robertson, Seymour & Thomas (1993b).
- ^ Kostochka (1984); Thomason (2001). Písmena O a Ω v těchto výrazech vyvolávají velká O notace.
- ^ Robertson, Seymour & Thomas (1993a).
- ^ Eppstein (2009).
- ^ A b Alon, Lingas & Wahlen (2007)
- ^ Robertson, Seymour & Thomas (1991).
- ^ Fomin, Oum & Thilikos (2010).
- ^ Pokud je funkce F je menší monotónní, pak pokud H je nezletilá z G pak f (H) ≤ f (G).
Reference
- Alon, Noga; Lingas, Andrzej; Wahlen, Martin (2007), „Přibližování maxima kliky minor a některých problémů s homeomorfismem podgrafu“ (PDF), Teoretická informatika, 374 (1–3): 149–158, doi:10.1016 / j.tcs.2006.12.021.
- Bollobás, B.; Catlin, P. A .; Erdős, Paul (1980), „Hadwigerova domněnka platí téměř pro každý graf“ (PDF), European Journal of Combinatorics, 1: 195–199, doi:10.1016 / s0195-6698 (80) 80001-1.
- Eppstein, David (2009), „Najít velké nezletilé kliky je těžké“, Journal of Graph Algorithms and Applications, 13 (2): 197–204, arXiv:0807.0007, doi:10,7155 / jgaa.00183.
- Fomin, Fedor V .; Oum, Sang-il; Thilikos, Dimitrios M. (2010), „Rank-width a tree-width of Hbezvýznamné grafy ", European Journal of Combinatorics, 31 (7): 1617–1628, arXiv:0910.0079, doi:10.1016 / j.ejc.2010.05.003.
- Hadwiger, Hugo (1943), „Über eine Klassifikation der Streckenkomplexe“, Vierteljschr. Naturforsch. Ges. Curych, 88: 133–143.
- Halin, Rudolf (1976), "S-funkce pro grafy ", J. Geometrie, 8 (1–2): 171–186, doi:10.1007 / BF01917434, PAN 0444522.
- Kostochka, A. V. (1984), „Dolní mez Hadwigerova počtu grafů podle jejich průměrného stupně“, Combinatorica, 4 (4): 307–316, doi:10.1007 / BF02579141.
- Robertson, Neil; Seymour, Paule; Thomas, Robin (1991), „Vyjma nekonečných nezletilých“, Diskrétní matematika, 95 (1–3): 303–319, doi:10.1016 / 0012-365X (91) 90343-Z, PAN 1141945.
- Robertson, Neil; Seymour, Paule; Thomas, Robin (1993a), „Hadwigerova domněnka o K.6-bezplatné grafy " (PDF), Combinatorica, 13 (3): 279–361, doi:10.1007 / BF01202354.
- Robertson, Neil; Seymour, P. D.; Thomas, Robin (1993b), „Linkless embeddings of graphs in 3-space“, Bulletin of the American Mathematical Society, 28 (1): 84–89, arXiv:matematika / 9301216, doi:10.1090 / S0273-0979-1993-00335-5, PAN 1164063.
- Thomason, Andrew (2001), „Extrémní funkce pro úplné nezletilé“, Journal of Combinatorial Theory, Řada B, 81 (2): 318–338, doi:10.1006 / jctb.2000.2013.
- Wagner, K. (1937), „Über eine Eigenschaft der ebenen Komplexe“, Matematika. Ann., 114: 570–590, doi:10.1007 / BF01594196.