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) vagy G homomorfizmus-foka (homomorphism degree). 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 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 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, 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.
Ritkaság Bármely, n csúcsú és k Hadwiger-számú gráf éleinek száma O(nk ). Ez a korlát éles: minden k értékre létezik olyan, k Hadwiger-számú gráf, melyben Ω(nk ) él van.; . A képletekben szereplő O és Ω betűk az O jelölésre utalnak. 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 ). Ezért a korlátos Hadwiger-számú gráfok ritka gráfok.
Színezé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.
Alacsony degeneráltsági értékük miatt a legfeljebb k Hadwiger-számú gráfok mohó színezési algoritmussal O(k ) színnel színezhetők.
Számítási bonyolultság Annak tesztelése, hogy egy konkrét gráf Hadwiger-száma elér-e egy adott k értéket NP-teljes feladat, 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. 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).
Kapcsolódó fogalmak 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.
Bármely k Hadwiger-számú gráfnak legfeljebb n2O(k log log k) klikkje (teljes részgráfja) lehet.
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,Az f függvény akkor minor-monoton, ha fennáll, hogy ha H a G minora, akkor f(H) ≤ f(G). é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
Jegyzetek
. . . . . . . . . . . .
Kategória:Gráfinvariánsok Kategória:Gráfminorok