„Hiperkockagráf” változatai közötti eltérés

A '''hiperkockagrá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.

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:          

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

[[Fájl:Hiperkockagrafok.gif|közép|400px|Alacsony dimenziójú (hiper)kockagráfok standard címkékkel]]                                                                                                                                                      

[[Fájl:7dimHiperkockagraf.jpg|thumb|A 7 dimenziós (hiper)kockagráf]]                              

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-gyel 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.)

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

'''8)''' Minden h≤2ⁿ páros szám esetén <math>H_n</math>-ben van h hosszúságú kör.     

'''11)''' <math>H_n</math> '''[[páros gráf]]''' (kétpólusú gráf).  

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<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/97704151.g4.png

* 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       

[[Fájl:H4-Hamilton-kore.gif|thumb|A 4 dimenziós (hiper)kockagráf Hamilton-körének indukciós szerkesztése]]