Hiperkockagráf

Ez a szócikk vagy szakasz lektorálásra, tartalmi javításokra szorul. A felmerült kifogásokat a szócikk vitalapja részletezi (vagy extrém esetben a szócikk szövegében elhelyezett, kikommentelt szövegrészek). Ha nincs indoklás a vitalapon (vagy szerkesztési módban a szövegközben), bátran távolítsd el a sablont! Csak akkor tedd a lap tetejére ezt a sablont, ha az egész cikk megszövegezése hibás. Ha nem, az adott szakaszba tedd, így segítve a lektorok munkáját!

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

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

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

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

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 Juhász Máté tette közzé.^[2]

Tulajdonságaik

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

1) ${\displaystyle H_{n}}$-nek 2ⁿ csúcsa van (${\displaystyle c_{n}=2^{n}}$), és a címkék az összes n hosszúságú 0-1 sorozatok.

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

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

4) ${\displaystyle 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 ${\displaystyle H_{0}}$-ban nincs két szomszédos csúcs. Ha ${\displaystyle H_{n+1}}$-ben a két csúcs ugyanabban a ${\displaystyle 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ő ${\displaystyle 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) ${\displaystyle 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) ${\displaystyle H_{n}}$ minden köre páros hosszúságú. (Bizonyítás: következik 4)-ből.)

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

(Bizonyítás: n=2 esetén H₂=C₄ (négyzet). Mivel ${\displaystyle H_{n+1}}$ két példány ${\displaystyle 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.)

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

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

9) ${\displaystyle 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) ${\displaystyle H_{n}}$ derékbősége (legrövidebb körének hossza) 4.

11) ${\displaystyle 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) ${\displaystyle 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 ${\displaystyle \left\lceil {\frac {d+3}{2}}\right\rceil \leq \chi _{s}(H_{d})\leq d+1.}$^[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]

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.