Hiperkockagráf
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.

Definíció 
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:

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

Tulajdonságaik 
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.)

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 

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.

Jegyzetek

Források 
 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.

Gráfelmélet
Parametrikus gráfcsaládok
Reguláris gráfok
Kocka
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 . Definíció 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ó : Adimenzió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ú,ésszá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é aszámjegyet , a másik példány csúcsainak címkéi elé azszámjegyet írjuk . Az alábbi ábrán néhány kisebb dimenziós kockagráfot mutatunk be , standard címkéikkel együtt : Magasabb dimenziós kockagráfokat Szalkai István honlapján találhatunk . A kockagráfok egy másik érdekes ábrázolását találhatjuk Juhsz Máté tette közzé . Tulajdonságaik Az alábbi állításokat általában indukcióval igazolhatjuk tetszőleges n természetes számra ( n≥0 ) : 1 ) -nek csúcsa van ( ) , és a címkék az összes n hosszúságú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étval , míg a másikatgyel 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övetkezikbő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 . ) 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övetkezikből . ) 10 ) derékbősége ( legrövidebb körének hossza ) 11 ) páros gráf ( kétpólusú gráf ) . ( Bizonyítás : következikból , vagy közvetlenül : a páros illetve a páratlan sokszá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 Aéstulajdonsá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 . Jegyzetek Források Szalkai István : Diszkrét matematika és algoritmuselmélet alapjai , Pannon Egyetemi Kiadó , Szalkai István : Diszkrét matematika feladatgyűjtemény , Pannon Egyetemi Kiadó , Gráfelmélet Parametrikus gráfcsaládok Reguláris gráfok Kocka