|
A '''hiperkocka-gráfokhiperkockagráfok''' (röviden csak '''kockagráfok''', '''cubic graphs''') a [[hiperkocka|hiperkockák]] élgráfjai (a csúcsok és élek gráfja). E speciális gráfok nem csak a gráfelméletben fontosak, hanem sokrétű alkalmazásuk van a műszaki életben, elektronikai áramkörök elméletében és a matematikai logikában is.
== Definíció ==
Mivel a magasabb dimenziós [[hiperkocka|hiperkockákat]] kettőzéssel és eltolással kapjuk, ezért élgráfjaik nyilván az alábbi definícióval határozhatók meg, a dimenzióra történő (matematikai) [[Teljes indukció|indukcióval]] :
'''Definíció:''' A 0 -dimenziós '''kockagráf''' egyetlen csúcs, él nélkül, jele <math>H_0</math> . Ha már <math>H_n</math> , az n dimenziós kockagráf elkészült, akkor <math>H_{n+1}</math> , a következő dimenziós kockagráf a következő: vegyünk két példány <math>H_n</math> -et, csúcsaik és éleik mellé még új éleket rajzolunk: a két <math>H_n</math> azonos csúcsait kössük össze egy-egy új éllel.
Vagyis <math>H_{n+1}</math> -nek kétszer annyi csúcsa van, mint <math>H_n</math> -nek, továbbá éleinek száma = kétszer <math>H_n</math> éleinek száma + az új élek száma: <math>c_{n+1}=2c_{n}</math> és <math>e_{n+1}=2e_{n}+c_{n}</math> , ahol <math>c_{n}</math> és <math>e_{n}</math> jelöli <math>H_n</math> csúcsainak és éleinek számát, valamint <math>c_{0}=1</math> és <math>e_{0}=0</math> .
A továbbiakban hasznos lesz <math>H_n</math> csúcsaihoz ''címkéket'' írnunk:
Az alábbi ábrán néhány, kisebb dimenziós kockagráfot mutatunk be, standard címkéikkel együtt:
[[Fájl:Hiperkockagrafok.gif|thumb|Alacsony dimenziójú (hiper)kocka-gráfokkockagráfok standard címkékkel]]
[[Fájl:7dimHiperkockagraf.jpg|thumb|A 7 dimenziós (hiper)kocka-gráfkockagráf]]
Magasabb dimenziós kockagráfokat <ref name=":0">'''Szalkai István:''' ''Oktatói honlap,'' http://math.uni-pannon.hu/~szalkai/DiB-kieg.html, http://math.uni-pannon.hu/~szalkai/
</ref>-ben találhatunk. <ref>'''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 </ref>-ben a kockagráfok egy másik, érdekes ábrázolását találhatjuk.
== Tulajdonságaik ==
Az alábbi állításokat általában [[Teljes indukció|indukcióval]] igazolhatjuk tetszőleges n természetes számra (n≥0):
'''1)''' <math>H_n</math> -nek 2ⁿ csúcsa van (<math>c_n=2^n</math>), és a címkék az ''összes'' n -hosszúságú 0-1 sorozatok.
'''2)''' <math>H_n</math> minden csúcsának fokszáma n , vagyis <math>H_n</math> [[Reguláris gráf|n-reguláris gráf]] .
'''3)''' <math>H_n</math> -nek <math>(2^n*n)/2 = n*2^{n-1}</math> éle van.
'''4)''' <math>H_n</math> -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 <math>H_0</math> -ban nincs két szomszédos csúcs. Ha <math>H_{n+1}</math> -ben a két csúcs ugyanabban a <math>H_n</math> példányban van, akkor az indukciós feltevés miatt az állítás igaz. Ha pedig két különböző <math>H_n</math> 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 -elgyel bővítettük.)
'''5)''' <math>H_n</math> -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)''' <math>H_n</math> minden köre páros hosszúságú. ('''Bizonyítás:''' következik 4)-ből.)
'''7)''' n≥2 esetén <math>H_n</math> -ben van [[Hamilton-kör]] .
('''Bizonyítás:''' n=2 esetén H₂=C₄ (négyzet). Mivel <math>H_{n+1}</math> két példány <math>H_n</math> -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 7) és 9) tulajdonságok alapján tehát könnyen felírhatunk bármilyen (páros) hosszúságú
[[Gray-kód|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 <ref name=":0">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
</ref>-ben megtalálhatjuk.
A kockagráfokról további olvasnivalókat <ref>'''Szalkai István:''' ''Diszkrét matematika és algoritmuselmélet alapjai'', Pannon Egyetemi Kiadó, 2000, http://webshop.uni-pannon.hu/index.php?option=com_virtuemart&view=productdetails&virtuemart_product_id=107&virtuemart_category_id=18 </ref> és <ref>'''Szalkai István:''' ''Diszkrét matematika feladatgyűjtemény,'' Pannon Egyetemi Kiadó, 1997, http://webshop.uni-pannon.hu/index.php?option=com_virtuemart&view=productdetails&virtuemart_product_id=108&virtuemart_category_id=18 </ref>-ben találhatunk.
[[Fájl:H4-Hamilton-kore.gif|thumb|A 4 dimenziós (hiper)kocka-gráfkockagráf Hamilton -körének indukciós szerkesztése]]
| 