Hiperkocka grafikon

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. március 17-én felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

Hiperkocka grafikon

Csúcsok	2n _
borda	2n − 1n _
Átmérő	n
Heveder	4, ha n ≥2
Automorfizmusok	n ! 2n _
Kromatikus szám	2
Spectrum	${\displaystyle \{(n-2k)^{\binom {n}{k));k=0,\ldots ,n\))$
Tulajdonságok	Szimmetrikus ketrec Moore gráf távolság-szabályos távolság-tranzitív Hamilton - egység távolságok kétszikű
Kijelölés	Qn_ _
Médiafájlok a Wikimedia Commons oldalon

A gráfelméletben a Q n hiperkocka gráf egy szabályos gráf , amelynek 2 n csúcsa, 2 n −1 n éle és n éle konvergál egy csúcsban. Megszerezhető egy geometriai hiperkocka egydimenziós vázaként . Például a Q 3 egy gráf, amelyet egy háromdimenziós kocka 8 csúcsa és 12 éle alkot. A gráf más módon is előállítható, egy n elemű halmaz részhalmazainak családjából kiindulva , az összes részhalmazt csúcsként használva, és két csúcsot összekötve egy éllel, ha a megfelelő halmazok csak egy elemben különböznek egymástól.

A hiperkocka gráfokat nem szabad összetéveszteni a köbös gráfokkal , amelyekben pontosan három él konvergál minden csúcsban. Az egyetlen hiperkocka, amelynek gráfja köbös, a Q 3 .

Épület

A Q n hiperkocka gráf egy n elemű halmaz részhalmazainak családjából szerkeszthető úgy, hogy az összes részhalmazt csúcsként használjuk, és két csúcsot összekötünk egy éllel, ha a megfelelő halmazok csak egy elemben különböznek egymástól. Ezenkívül 2n csúcsból is fel lehet építeni egy gráfot , n - bites bináris számokkal címkézve azokat, és csúcspárokat élekkel összekötve, ha a megfelelő címkéik közötti Hamming-távolság 1. Ez a két konstrukció szorosan összefügg – a bináris számokat így is ábrázolhatjuk. halmazok (pozíciók halmaza, ahol egybe kerül), és két ilyen halmaz egy elemben különbözik, ha a megfelelő két bináris szám közötti Hamming-távolság 1.

Q n+1 két Q n hiperkocka diszjunkt uniójából állítható elő úgy, hogy Q n egyik másolatának minden csúcsából éleket adunk a másik másolat megfelelő csúcsához, amint az az ábrán látható. Az összekötő élek illeszkedést alkotnak .

A Q n másik definíciója n teljes , két csúcsot tartalmazó K 2 gráf közvetlen szorzata .

Példák

A Q 0 gráf egyetlen csúcsból áll, a Q 1 gráf két csúcsú teljes gráf , a Q 2 pedig egy 4 hosszúságú ciklus .

A Q 3 gráf egy 1-vázas kocka , nyolc csúcsú és tizenkét élű síkgráf.

A Q 4 gráf a Möbius konfiguráció Levi-gráfja .

Tulajdonságok

Bipartite

Minden hiperkocka gráf kétrészes – csúcsai csak két színnel színezhetők . Ennek a színezésnek a két színe megtalálható a hiperkocka gráfok részhalmazainak megalkotásakor úgy, hogy egy színt rendelünk a páros elemszámú részhalmazokhoz, és egy másik színt a páratlan számú elemet tartalmazó részhalmazokhoz.

Hamiltoni ciklusok

Minden olyan Q n hiperkockának , amelynek n > 1 van egy Hamilton-ciklusa , amely minden csúcson pontosan egyszer halad át. Ezen túlmenően egy Hamilton-útvonal az u, v csúcsok között akkor és csak akkor létezik, ha u és v különböző színűek a gráf kétszínű színezésében. Mindkét tény könnyen ellenőrizhető indukcióval egy hipergráf dimenzióján, egy hiperkocka gráf felépítésével két kisebb hiperkocka összekapcsolásával.

A hiperkocka fent leírt tulajdonságai szorosan összefüggenek a Gray kódok elméletével . Pontosabban, bijektív megfelelés van az n bites ciklikus Gray-kódok halmaza és a Q n hiperkockában található Hamilton-ciklusok halmaza között . [1] Hasonló tulajdonság érvényes az aciklikus n bites Gray kódokra és a Hamilton-útvonalakra.

Kevésbé ismert az a tény, hogy a hiperkockában minden tökéletes illeszkedést ki lehet terjeszteni egy Hamilton-ciklusra. [2] Nyitott marad a kérdés, hogy ki lehet-e terjeszteni egy párosítást egy Hamilton-ciklusra. [3]

Egyéb tulajdonságok

Hiperkocka gráf Q n (n > 1):

egy véges Boole-algebra Hasse-diagramja ;
a medián gráf . Bármely medián gráf a hiperkocka izometrikus részgráfja, és a hiperkocka csonkolásával alakítható ki;
több mint 2 2 n-2 tökéletes illeszkedéssel rendelkezik (ez egy másik következmény az induktív konstrukcióból);
ívtranzitív és szimmetrikus . _ A hiperkocka gráfszimmetriák előjeles permutációként ábrázolhatók, az automorfizmus csoport izomorf ; $S_{n}\wr \mathbb {Z} _{2}$
tartalmazza az összes 4, 6, ..., 2 n hosszúságú ciklust, ezért egy bipanciklikus gráf ;
egységnyi távolsággráfként rajzolható meg az euklideszi síkon úgy, hogy a halmaz minden eleméhez egységvektort választunk , és az S halmaznak megfelelő csúcsokat az S -ből származó vektorok összegének megfelelő pontba helyezzük ;
Balinsky tétele szerint egy csúcs - n - összefüggő gráf ;
akkor és csak akkor sík ( metszéspontok nélkül rajzolható ), ha n ≤ 3. Nagy n érték esetén a hiperkocka [4] [5] nemzetséggel rendelkezik ; $(n-4)2^{n-3}+1$

pontosan átívelő fákkal rendelkezik [5] ; ${\displaystyle 2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \válasszon k))$
a Q n család (n > 1) Levi-gráfok családja ;
ismert, hogy a Q n gráf akromatikus száma arányos -vel , de a pontos arányossági állandó nem ismert [6] ; ${\displaystyle {\sqrt {n2^{n))))$

a Q n gráf sávjának szélessége pontosan egyenlő a -val. [7] ; $\sum _{i=0}^{n}{\binom {n}{\lfloor n/2\rfloor ))$
az előfordulási mátrix sajátértékei (-n,-n+2,-n+4,…,n-4,n-2,n), a gráf Kirchhoff-mátrixának sajátértékei pedig: 0,2,…,2n);
az izoperimetrikus szám h(G)=1.

Feladatok

Az adott hiperkocka gráf generált részgráfjaként a leghosszabb út vagy ciklus megtalálásának problémája a kígyó a dobozban problémaként ismert .

Szymanski hipotézise a hiperkocka alkalmasságára vonatkozik azadatcsere hálózati topológiájaként . A hipotézis azt állítja, hogy akárhogyan is rendezzük át egy gráf csúcsait, mindig vannak olyan (irányított) utak, amelyek csúcsokat kötnek össze a képeikkel, hogy két különböző csúcsot összekötő út ne haladjon át ugyanazon az élen ugyanabban az irányban [8] .

Lásd még

Köbös kapcsolt ciklusok
Fibonacci kocka
Halmozott kockagrafikon
Felezett kockagrafikon

Jegyzetek

↑ Malmok. Néhány teljes ciklus az n-kockáról // Proceedings of the American Mathematical Society. - American Mathematical Society, 1963. - V. 14 , no. 4 . — S. 640–643 . - doi : 10.2307/2034292 . — . .
↑ Perfect matchings to Hamilton-cycles in hypercubes // Journal of Combinatorial Theory, Series B. - 2007. - Vol. 97 . – S. 1074–1076 . - doi : 10.1016/j.jctb.2007.02.007 . .
↑ Ruskey, F. és Savage, C. Az egyezések kiterjednek a Hamilton-ciklusokra hiperkockákban Archiválva : 2021. május 6., a Wayback Machine on Open Problem Garden. 2007.
↑ G. Ringel. ber drei kombinatorische Probleme am n-dimensionalen Wiirfel und Wiirfelgitter // Abh. Math. fonnyadt. Univ. Hamburg. - 1955. - T. 20 . - S. 10-19 .
↑ 1 2 Frank Harary, John P. Hayes, Horng-Jyh Wu. Áttekintés a hiperkocka gráfok elméletéről // Számítógépek és matematika alkalmazásokkal. - 1988. - T. 15 , sz. 4 . – S. 277–289 . - doi : 10.1016/0898-1221(88)90213-1 . .
↑ Y. Roichman. A hiperkockák akromatikus számáról // Journal of Combinatorial Theory, Series B. - 2000. - Vol. 79 , no. 2 . – S. 177–182 . - doi : 10.1006/jctb.2000.1955 . .
↑ Optimális számozás és izoperimetriai problémák a grafikonokon, LH Harper, Journal of Combinatorial Theory , 1, 385-393, doi : 10.1016/S0021-9800(66)80059-5
↑ Ted H. Szymanski. Proc. Internat. Konf. a párhuzamos feldolgozásról. - Silver Spring, MD: IEEE Computer Society Press, 1989. - V. 1. - S. 103–110. .

Linkek

F. Harary, JP Hayes, H.-J. wu. Áttekintés a hiperkocka gráfok elméletéről // Számítógépek és matematika alkalmazásokkal . - 1988. - T. 15 , sz. 4 . – S. 277–289 . - doi : 10.1016/0898-1221(88)90213-1 . .