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
formázás, még kell
formázás, még kell
12. sor:
'''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|thumbkö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]]                              
 
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.
</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):                              
27 ⟶ 25 sor:
'''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.)     
A lap eredeti címe: „https://hu.wikipedia.org/wiki/Hiperkockagráf”