Hiperkockagráf

Sablon:Lektor Sablon:Gráf infobox 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 $\lceil \frac{d+3}{2}\rceil \le {\chi }_s(H_d)\le 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.