Wikipédia

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

Laptörténet interaktív böngészése
[nem ellenőrzött változat][nem ellenőrzött változat]
← Régebbi szerkesztésÚjabb szerkesztés →
Tartalom törölve Tartalom hozzáadva
VizuálisWikiszöveges
aNincs szerkesztési összefoglaló
formázás, még kell
39. sor:
'''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ör|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.     
 
'''9)''' <math>H_n</math> minden körében a csúcsok standard címkéi [[Gray-kód|Gray-kódot]]ot alkotnak. ('''Bizonyítás:''' következik 4)-ből.)
 
'''10)''' <math>H_n</math> [[Girthparaméter|derékbősége]] (legrövidebb körének hossza) 4 .
 
'''11)''' <math>H_n</math> '''[[páros gráf]]''' (kétpólusú gráf).  
 
('''Bizonyítás:''' következik 6) -ból, vagy közetlenülkö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)''' <math>H_n</math> '''[[Átmérő (gráfelmélet)|átmérője]]''' (leghosszabb egyszerű útjának hossza) n .
 
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,
 
[[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
66 ⟶ 64 sor:
</ref>-ben megtalálhatjuk.
 
== Jegyzetek ==
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.       ▼
{{jegyzetek}}
 
== Külső hivatkozások ==
▲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.       
* 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]]          
A lap eredeti címe: „https://hu.wikipedia.org/wiki/Hiperkockagráf”