Hiperkockagráf

matematikai fogalom a gráfelméletben

A hiperkockagráfok hiperkockák csúcsai és élei alkotta gráfok. Sokrétűen alkalmazzák őket a műszaki életben, az elektronikai áramkörök elméletében és a matematikai logikában is.

Hiperkockagráf
Q4 hiperkockagráf
Q4 hiperkockagráf

Csúcsok száma 2n
Élek száma 2n−1n
Átmérő n
Derékbőség 4, ha n ≥ 2
Kromatikus szám 2
Automorfizmusok n! 2n
Spektrum
Jelölés Qn

DefinícióSzerkesztés

Mivel a magasabb dimenziós hiperkockákat kettőzéssel és eltolással kapjuk, ezért a hiperkockagráfok az alábbi definícióval határozhatók meg, a dimenzióra történő (matematikai) indukcióval:

Definíció: A 0 dimenziós kockagráf egyetlen csúcs, él nélkül, jele  . Ha már  , az n dimenziós kockagráf elkészült, akkor  , a következő dimenziós kockagráf a következő: vegyünk két példány  -et, csúcsaik és éleik mellé még új éleket rajzolunk: a két   azonos csúcsait kössük össze egy-egy új éllel.

Vagyis  -nek kétszer annyi csúcsa van, mint  -nek, továbbá éleinek száma = kétszer   éleinek száma + az új élek száma:   és  , ahol   és   jelöli   csúcsainak és éleinek számát, valamint   és  .

A továbbiakban hasznos lesz   csúcsaihoz címkéket írnunk:

Definíció: A   gráf minden csúcsához egy n hosszú, 0 és 1 számjegyekből álló sorozatot, a csúcs standard címkéjét írjuk.   egyetlen csúcsához az üres sorozatot („semmit”) írjuk. Mivel   csúcsai két példány   csúcsaiból állnak, ezért az egyik példány   csúcsainak címkéi elé a 0 számjegyet, a másik példány   csúcsainak címkéi elé az 1 számjegyet írjuk.

Az alábbi ábrán néhány kisebb dimenziós kockagráfot mutatunk be, standard címkéikkel együtt:

 
A 7 dimenziós (hiper)kockagráf

Magasabb dimenziós kockagráfokat Szalkai István honlapján[1] találhatunk. A kockagráfok egy másik érdekes ábrázolását találhatjuk Juhsz Máté tette közzé.[2]

TulajdonságaikSzerkesztés

Az alábbi állításokat általában indukcióval igazolhatjuk tetszőleges n természetes számra (n≥0):

1)  -nek 2ⁿ csúcsa van ( ), és a címkék az összes n hosszúságú 0-1 sorozatok.

2)   minden csúcsának fokszáma n , vagyis   n-reguláris gráf.

3)  -nek   éle van.

4)  -ben bármely két csúcs pontosan akkor van éllel összekötve, ha standard címkéjük pontosan egy helyiértékben különbözik.

(Bizonyítás: n=0 esetén  -ban nincs két szomszédos csúcs. Ha  -ben a két csúcs ugyanabban a   példányban van, akkor az indukciós feltevés miatt az állítás igaz. Ha pedig két különböző   példányban vannak, akkor a konstrukció miatt pontosan akkor vannak összekötve, ha eredeti címkéjük megegyezett, de most egyikük címkéjét 0-val, míg a másikat 1-gyel bővítettük.)

5)  -ben bármely két csúcs távolsága (közöttük levő legrövidebb út hossza) éppen annyi, mint ahány helyiértéken a (standard) címkéjük eltér egymástól.

6)   minden köre páros hosszúságú. (Bizonyítás: következik 4)-ből.)

7) n≥2 esetén  -ben van Hamilton-kör.

(Bizonyítás: n=2 esetén H₂=C₄ (négyzet). Mivel   két példány  -ből áll, és mindkét példányban az indukciós feltétel szerint van egy-egy Hamilton-kör, ezért ezt a két Hamilton-kört azonos helyen megszakítjuk, és a szakítások helyén a megfelelő végpontokat összekötő új élekkel e két megszakított összekötjük.)

 
A 4 dimenziós (hiper)kockagráf Hamilton-körének indukciós szerkesztése

Például n=4 esetén az alábbi Hamilton-kört kapjuk:

8) Minden h≤2ⁿ páros szám esetén  -ben van h hosszúságú kör.

9)   minden körében a csúcsok standard címkéi Gray-kódot alkotnak. (Bizonyítás: következik 4)-ből.)

10)   derékbősége (legrövidebb körének hossza) 4.

11)   páros gráf (kétpólusú gráf).

(Bizonyítás: következik 6)-ból, vagy közvetlenül: a páros illetve a páratlan sok 1 számjegyet tartalmazó címkéjű csúcsok alkotják a két pólust (osztályt).)

12)   átmérője (leghosszabb egyszerű útjának hossza) n.

13) Egységtávolsággráf.

14) A d dimenziós Hd hiperkocka χs csillagkromatikus számára igaz, hogy  [3]

A 7) és 9) tulajdonságok alapján tehát könnyen felírhatunk bármilyen (páros) hosszúságú Gray-kódsorozatot, ami a kockagráfok egyik legfontosabb felhasználási területe. Például H₇ Hamilton-körének megszerkesztését és a kapott Gray-kódot Szalkai István könyvében megtalálhatjuk.[4]

JegyzetekSzerkesztés

  1. Szalkai István: Oktatói honlap, http://math.uni-pannon.hu/~szalkai/DiB-kieg.html, http://math.uni-pannon.hu/~szalkai/
  2. Juhász Máté: Hogyan rajzoljunk n dimenziós kockát?, KöMaL, 1999/2, http://db.komal.hu/scan/1999/02/99902130.png, http://db.komal.hu/scan/1999/02/99902063.png
  3. Fertin, Guillaume; Raspaud, André & Reed, Bruce (2004), "Star coloring of graphs", Journal of Graph Theory 47 (3): 163–182, DOI 10.1002/jgt.20029
  4. Szalkai István: Mit tudhat egy számolóléc?, KöMaL 1977. http://math.uni-pannon.hu/~szalkai/Szalkai-1977-KoMaL.pdf, http://db.komal.hu/scan/1977/04/97704146.g4.png http://db.komal.hu/scan/1977/04/97704151.g4.png

ForrásokSzerkesztés

  • Szalkai István: Diszkrét matematika és algoritmuselmélet alapjai, Pannon Egyetemi Kiadó, 2000.
  • Szalkai István: Diszkrét matematika feladatgyűjtemény, Pannon Egyetemi Kiadó, 1997.