Hiperkockagráf

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	$\{(n-2k)^{\binom {n}{k}};k=0,\ldots ,n\}$
Jelölés	Qn

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 $H_{0}$. Ha már $H_{n}$, az n dimenziós kockagráf elkészült, akkor $H_{n+1}$, a következő dimenziós kockagráf a következő: vegyünk két példány $H_{n}$-et, csúcsaik és éleik mellé még új éleket rajzolunk: a két $H_{n}$ azonos csúcsait kössük össze egy-egy új éllel.

Vagyis $H_{n+1}$-nek kétszer annyi csúcsa van, mint $H_{n}$-nek, továbbá éleinek száma = kétszer $H_{n}$ éleinek száma + az új élek száma: $c_{n+1}=2c_{n}$ és $e_{n+1}=2e_{n}+c_{n}$, ahol $c_{n}$ és $e_{n}$ jelöli $H_{n}$ csúcsainak és éleinek számát, valamint $c_{0}=1$ és $e_{0}=0$.

A továbbiakban hasznos lesz $H_{n}$ csúcsaihoz címkéket írnunk:

Definíció: A $H_{n}$ 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. $H_{0}$ egyetlen csúcsához az üres sorozatot („semmit”) írjuk. Mivel $H_{n+1}$ csúcsai két példány $H_{n}$ csúcsaiból állnak, ezért az egyik példány $H_{n}$ csúcsainak címkéi elé a 0 számjegyet, a másik példány $H_{n}$ 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:

Alacsony dimenziójú (hiper)kockagráfok standard címkékkel

A 7 dimenziós (hiper)kockagráf

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 Juhász 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) $H_{n}$-nek 2ⁿ csúcsa van ($c_{n}=2^{n}$), és a címkék az összes n hosszúságú 0-1 sorozatok.

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

3) $H_{n}$-nek $(2^{n}\cdot n)/2=n\cdot 2^{n-1}$ éle van.

4) $H_{n}$-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 $H_{0}$-ban nincs két szomszédos csúcs. Ha $H_{n+1}$-ben a két csúcs ugyanabban a $H_{n}$ példányban van, akkor az indukciós feltevés miatt az állítás igaz. Ha pedig két különböző $H_{n}$ 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) $H_{n}$-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) $H_{n}$ minden köre páros hosszúságú. (Bizonyítás: következik 4)-ből.)

7) n≥2 esetén $H_{n}$-ben van Hamilton-kör.

(Bizonyítás: n=2 esetén H₂=C₄ (négyzet). Mivel $H_{n+1}$ két példány $H_{n}$-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 $H_{n}$-ben van h hosszúságú kör.

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

10) $H_{n}$ derékbősége (legrövidebb körének hossza) 4.

11) $H_{n}$ 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) $H_{n}$ átmérője (leghosszabb egyszerű útjának hossza) n.

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

14) A d dimenziós H_d hiperkocka χ_s csillagkromatikus számára igaz, hogy $\left\lceil {\frac {d+3}{2}}\right\rceil \leq \chi _{s}(H_{d})\leq d+1.$

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.

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.