French
DeutschHadwiger-szám – Wikipédia
A matematika, azon belül a gráfelmélet területén egy G irányítatlan gráf Hadwiger-száma annak a legnagyobb teljes gráfnak a mérete, ami G éleinek összehúzásával előállítható. Ezzel ekvivalens megfogalmazás szerint a h(G) Hadwiger-szám megegyezik annak a legnagyobb Kk teljes gráfnak a k méretével, ami G-nek minora, azaz előállítható belőle az élösszehúzás, csúcstörlés és éltörlés műveletek segítségével. Úgy is ismert, mint G összehúzási klikkszáma (contraction clique number)[1] vagy G homomorfizmus-foka (homomorphism degree).[2] Nevét Hugo Hadwigerről kapta, aki 1943-ban a Hadwiger-sejtés kapcsán bevezette; a sejtés állítása szerint a Hadwiger-szám minden esetben legalább akkora, mint G kromatikus száma.
A legfeljebb négy Hadwiger-számú gráfok jellemzését (Wagner 1937) végezte el. A korlátos Hadwiger-számú gráfok ritkák, kromatikus számuk alacsony. Egy gráf Hadwiger-számának megállapítása NP-nehéz, de rögzített paraméter mellett kezelhető.
Alacsony Hadwiger-számú gráfok
[szerkesztés]Egy G gráf Hadwiger-száma pontosan akkor legfeljebb kettő, ha az fa vagy erdő, mivel egy három csúcs alkotta teljes minor csak egy G-beli kör összehúzásával jöhet létre.
Egy gráf Hadwiger-száma pontosan akkor legfeljebb három, ha favastagsága legfeljebb kettő, ami akkor és csak akkor igaz, ha minden kétszeresen összefüggő komponense soros-párhuzamos gráf.
A síkbarajzolható gráfokat tiltott minoraik alapján jellemző Wagner-tétel alapján a síkbarajzolható gráfok Hadwiger-száma legfeljebb négy. Ugyanabban a cikkben, amiben a tételt is bizonyította, (Wagner 1937) elvégezte a legfeljebb négy Hadwiger-számú gráfok precízebb jellemzését is: ezek a gráfok, melyek létrehozhatók a nyolc csúcsú Wagner-gráfból és síkbarajzolható gráfokból a klikk-összeg művelet segítségével.
A legfeljebb öt Hadwiger-számú gráfok közé tartoznak a csúcsgráfok és a láncmentesen beágyazható gráfok, melyek közül mindkettőnek a tiltott minorai között szerepel a K6 teljes gráf.[3]
Ritkaság
[szerkesztés]Bármely, n csúcsú és k Hadwiger-számú gráf éleinek száma O(nk √log k). Ez a korlát éles: minden k értékre létezik olyan, k Hadwiger-számú gráf, melyben Ω(nk √log k) él van.[4] Ha a G gráf Hadwiger-száma k, akkor minden részgráfjára igaz, hogy Hadwiger-száma legfeljebb k, amiből következik, hogy G degeneráltsága O(k √log k). Ezért a korlátos Hadwiger-számú gráfok ritka gráfok.
Színezés
[szerkesztés]A Hadwiger-sejtés szerint a Hadwiger-szám legalább akkora, mint az adott gráf kromatikus száma. Tehát minden k Hadwiger-számú gráfnak kellene lennie legfeljebb k színt használó színezésének. A k = 4 eset (Wagner a 4-es Hadwiger-számú gráfokkal foglalkozó jellemzése alapján) ekvivalens a síkbarajzolható gráfokra vonatkozó négyszíntétellel, és a sejtést k ≤ 5-re bizonyították is, de k nagyobb értékeire nem ismert, hogy igaz-e.[5]
Alacsony degeneráltsági értékük miatt a legfeljebb k Hadwiger-számú gráfok mohó színezési algoritmussal O(k √log k) színnel színezhetők.
Számítási bonyolultság
[szerkesztés]Annak tesztelése, hogy egy konkrét gráf Hadwiger-száma elér-e egy adott k értéket NP-teljes feladat,[6] amiből következik, hogy a Hadwiger-szám meghatározása NP-nehéz. A probléma azonban rögzített paraméter mellett kezelhető: létezik a legnagyobb klikkminor megkeresésére szolgáló algoritmus, aminek futási ideje a gráf méretének polinom, h(G)-nek pedig exponenciális függvénye.[7] Ráadásul polinom idejű algoritmusokkal lényegesen jobban (pontosabban) közelíthető a Hadwiger-szám, mint a legnagyobb teljes részgráf keresésére szolgáló legjobb polinom idejű approximáció (feltéve, hogy P ≠ NP).[7]
Kapcsolódó fogalmak
[szerkesztés]Egy G gráf akromatikus száma a legnagyobb klikkjének mérete, ami előállítható G független csúcshalmazai egy családjának összehúzásával.
Végtelen gráfok megszámlálhatatlan klikkminorai jellemezhetők a bennük található menedékekkel, melyek az üldözős-menekülős játékok elkerülő stratégiáit formalizálják: ha a Hadwiger-szám nem megszámlálható, akkor megegyezik a gráf menedékei közül a legnagyobb rendűvel.[8]
Bármely k Hadwiger-számú gráfnak legfeljebb n2O(k log log k) klikkje (teljes részgráfja) lehet.[9]
(Halin 1976) egy S-függvények nevű gráfparaméter-osztályt definiál, melybe a Hadwiger-szám is beletartozik. Ezeknek a gráfokhoz egész számokat rendelő függvényeknek a következő tulajdonságokkal kell rendelkezniük: az üres gráfon legyen nulla az értékük, legyenek minor-monotonok,[10] értékük eggyel nőjön, ha az összes korábbi csúccsal szomszédos új csúcs kerül a gráfba, végül hogy egy klikk-szeparátor két oldalán lévő részgráfok értékei közül a nagyobbikat vegye fel. Az összes ilyen függvény halmaza az elemenkénti minimalizáció és maximalizáció műveleteire nézve teljes hálót alkot. A háló legkisebb eleme a Hadwiger-szám, legnagyobbik pedig a favastagság.
Fordítás
[szerkesztés]- Ez a szócikk részben vagy egészben a Hadwiger number című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek
[szerkesztés]- ↑ Bollobás, Catlin & Erdős (1980).
- ↑ Halin (1976).
- ↑ Robertson, Seymour & Thomas (1993b).
- ↑ (Kostochka 1984); (Thomason 2001). A képletekben szereplő O és Ω betűk az O jelölésre utalnak.
- ↑ Robertson, Seymour & Thomas (1993a).
- ↑ Eppstein (2009).
- ↑ a b (Alon, Lingas & Wahlen 2007)
- ↑ Robertson, Seymour & Thomas (1991).
- ↑ Fomin, Oum & Thilikos (2010).
- ↑ Az f függvény akkor minor-monoton, ha fennáll, hogy ha H a G minora, akkor f(H) ≤ f(G).
- Alon, Noga; Lingas, Andrzej & Wahlen, Martin (2007), "Approximating the maximum clique minor and some subgraph homeomorphism problems", Theoretical Computer Science 374 (1–3): 149–158, doi:10.1016/j.tcs.2006.12.021, <http://www.math.tau.ac.il/~nogaa/PDFS/lingas7.pdf>.
- Bollobás, B.; Catlin, P. A. & Erdős, Paul (1980), "Hadwiger's conjecture is true for almost every graph", European Journal of Combinatorics 1: 195–199, doi:10.1016/s0195-6698(80)80001-1, <http://www.renyi.hu/~p_erdos/1980-10.pdf>.
- Eppstein, David (2009), "Finding large clique minors is hard", Journal of Graph Algorithms and Applications 13 (2): 197–204, DOI 10.7155/jgaa.00183.
- Fomin, Fedor V.; Oum, Sang-il & Thilikos, Dimitrios M. (2010), "Rank-width and tree-width of H-minor-free graphs", European Journal of Combinatorics 31 (7): 1617–1628, DOI 10.1016/j.ejc.2010.05.003.
- Hadwiger, Hugo (1943), "Über eine Klassifikation der Streckenkomplexe", Vierteljschr. Naturforsch. Ges. Zürich 88: 133–143.
- Halin, Rudolf (1976), "S-functions for graphs", J. Geometry 8 (1-2): 171–186, DOI 10.1007/BF01917434.
- Kostochka, A. V. (1984), "Lower bound of the Hadwiger number of graphs by their average degree", Combinatorica 4 (4): 307–316, DOI 10.1007/BF02579141.
- Robertson, Neil; Seymour, Paul & Thomas, Robin (1991), "Excluding infinite minors", Discrete Mathematics 95 (1-3): 303–319, DOI 10.1016/0012-365X(91)90343-Z.
- Robertson, Neil; Seymour, Paul & Thomas, Robin (1993a), "Hadwiger's conjecture for K6-free graphs", Combinatorica 13 (3): 279–361, doi:10.1007/BF01202354, <http://www.math.gatech.edu/~thomas/PAP/hadwiger.pdf>. Hozzáférés ideje: 2018-12-02.
- 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, DOI 10.1090/S0273-0979-1993-00335-5.
- Thomason, Andrew (2001), "The extremal function for complete minors", Journal of Combinatorial Theory, Series B 81 (2): 318–338, DOI 10.1006/jctb.2000.2013.
- Wagner, K. (1937), "Über eine Eigenschaft der ebenen Komplexe", Math. Ann. 114: 570–590, DOI 10.1007/BF01594196.