Hadwiger-szám

A Wikipédiából, a szabad enciklopédiából
Egy gráf négy összefüggő részgráffal, melyek összehúzásával teljes gráf jön létre. A Wagner-tétel értelmében nincs ötcsúcsú teljes minora, ezért Hadwiger-száma pontosan négy.

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.

Két síkbarajzolható gráf és a Wagner-gráf klikkösszege egy négy Hadwiger-számú nagyobb gráf lesz.

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]

  1. ↑ Bollobás, Catlin & Erdős (1980).
  2. ↑ Halin (1976).
  3. ↑ Robertson, Seymour & Thomas (1993b).
  4. ↑ (Kostochka 1984); (Thomason 2001). A képletekben szereplő O és Ω betűk az O jelölésre utalnak.
  5. ↑ Robertson, Seymour & Thomas (1993a).
  6. ↑ Eppstein (2009).
  7. ↑ a b (Alon, Lingas & Wahlen 2007)
  8. ↑ Robertson, Seymour & Thomas (1991).
  9. ↑ Fomin, Oum & Thilikos (2010).
  10. ↑ Az f függvény akkor minor-monoton, ha fennáll, hogy ha H a G minora, akkor f(H) ≤ f(G).
A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Hadwiger-szám&oldid=25467951”