Graficul hipercubului

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 17 martie 2022; verificările necesită 3 modificări .

Graficul hipercubului

Vârfurile	2n _
coaste	2n − 1n _
Diametru	n
Circumferinţă	4 dacă n ≥2
Automorfisme	n ! 2n _
Număr cromatic	2
Spectru	$\{(n-2k)^{\binom {n}{k));k=0,\ldots, n\)$
Proprietăți	Cușcă simetrică Graficul Moore distanță-distanță regulată -distanțe unități hamiltoniene tranzitive dicotiledonate
Desemnare	Qn _
Fișiere media la Wikimedia Commons

În teoria grafurilor, un graf hipercub Q n este un graf obișnuit cu 2 n vârfuri, 2 n -1 n muchii și n muchii convergente la un vârf. Poate fi obținut ca un schelet unidimensional al unui hipercub geometric . De exemplu, Q 3 este un grafic format din 8 vârfuri și 12 muchii ale unui cub tridimensional. Graficul poate fi obținut în alt mod, pornind de la o familie de submulțimi ale unei mulțimi cu n elemente, folosind toate submulțimile ca vârfuri și conectând două vârfuri cu o muchie dacă mulțimile corespunzătoare diferă doar cu un element.

Graficele hipercubice nu trebuie confundate cu graficele cubice , în care exact trei muchii converg la fiecare vârf. Singurul hipercub al cărui grafic este cubic este Q 3 .

Clădire

Un grafic hipercub Q n poate fi construit dintr-o familie de submulțimi ale unei mulțimi cu n elemente folosind toate submulțimile ca vârfuri și conectând două vârfuri cu o muchie dacă mulțimile corespunzătoare diferă doar cu un element. De asemenea, un grafic poate fi construit folosind 2n vârfuri, etichetându-le cu numere binare de n biți și conectând perechi de vârfuri cu muchii dacă distanța Hamming dintre etichetele lor corespunzătoare este 1. Aceste două construcții sunt strâns legate - numerele binare pot fi reprezentate ca seturi (un set de poziții, unde costă unul) și două astfel de seturi diferă cu un element dacă distanța Hamming dintre cele două numere binare corespunzătoare este egală cu 1.

Q n+1 poate fi construit din uniunea disjunsă a două hipercuburi Q n prin adăugarea muchiilor de la fiecare vârf al unei copii a lui Q n la vârful corespondent al celeilalte copii, așa cum se arată în figură. Marginile de legătură formează o potrivire .

O altă definiție a lui Q n este produsul direct al n grafice complete K 2 care conțin două vârfuri.

Exemple

Graficul Q 0 constă dintr-un singur vârf, graficul Q 1 este un grafic complet cu două vârfuri, iar Q 2 este un ciclu de lungime 4.

Graficul Q 3 este un cub cu 1 schelet , un grafic plan cu opt vârfuri și douăsprezece muchii.

Graficul Q 4 este graficul Levi al configurației Möbius .

Proprietăți

Bipartit

Toate graficele hipercub sunt bipartite - vârfurile lor pot fi colorate doar cu două culori. Cele două culori ale acestei colorări pot fi găsite din construirea de subseturi de grafice hipercube prin alocarea unei culori subseturi care au un număr par de elemente și o altă culoare subseturi care au un număr impar de elemente.

Cicluri hamiltoniene

Orice hipercub Q n cu n > 1 are un ciclu hamiltonian care trece prin fiecare vârf exact o dată. În plus, o cale hamiltoniană între vârfurile u, v există dacă și numai dacă u și v au culori diferite într-o colorare în două culori a graficului. Ambele fapte pot fi ușor verificate prin inducerea dimensiunii unui hipergraf, cu construcția unui graf hipercub prin conectarea a două hipercuburi mai mici.

Proprietățile hipercubului descrise mai sus sunt strâns legate de teoria codurilor Gray . Mai precis, există o corespondență bijectivă între mulțimea de coduri Gray ciclice de n -biți și setul de cicluri hamiltoniene din hipercubul Q n . [1] O proprietate similară este valabilă pentru codurile Gray aciclice de n -biți și căile hamiltoniene.

Mai puțin cunoscut este faptul că orice potrivire perfectă într-un hipercub poate fi extinsă la un ciclu hamiltonian. [2] Întrebarea dacă orice potrivire poate fi extinsă la un ciclu hamiltonian rămâne deschisă. [3]

Alte proprietăți

Graficul hipercub Q n (n > 1):

este diagrama Hasse a unei algebre booleene finite ;
este graficul medianului . Orice grafic median este un subgraf izometric al hipercubului și poate fi format prin trunchierea hipercubului;
are mai mult de 2 2 n-2 potriviri perfecte (acesta este un alt corolar care rezultă din construcția inductivă);
este arc-tranzitiv și simetric . Simetriile grafului hipercub pot fi reprezentate ca permutări semnate, grupul de automorfism este izomorf ; $S_{n}\wr \mathbb {Z} _{2)$
conține toate ciclurile de lungime 4, 6, ..., 2 n și, prin urmare, este un grafic bipanciclic ;
poate fi desenat ca un grafic de distanță unitară pe planul euclidian alegând un vector unitar pentru fiecare element al mulțimii și plasând fiecare vârf corespunzător mulțimii S într-un punct corespunzător sumei vectorilor din S ;
este un graf de vârf - n -conectat prin teorema lui Balinsky ;
este plană (poate fi desenată fără intersecții) dacă și numai dacă n ≤ 3. Pentru valori mari ale lui n , hipercubul are genul [4] [5] ; $(n-4)2^{n-3}+1$

are copaci care se întind exact [5] ; $2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \alegeți k)$
familia Q n (n > 1) este o familie de grafuri Levi ;
se știe că numărul acromatic al graficului Q n este proporțional cu , dar constanta de proporționalitate exactă este necunoscută [6] ; ${\sqrt {n2^{n)})$

lăţimea benzii a graficului Q n este exact egală cu. [7] ; $\sum _{i=0}^{n}{\binom {n}{\lfloor n/2\rfloor ))$
valorile proprii ale matricei de incidență sunt (-n,-n+2,-n+4,…,n-4,n-2,n), iar valorile proprii ale matricei Kirchhoff a graficului sunt ( 0,2,…,2n);
numărul izoperimetric este h(G)=1.

Sarcini

Problema găsirii celui mai lung drum sau ciclu care este un subgraf generat al unui grafic hipercub dat este cunoscută sub numele de problema șarpelui într-o cutie .

Ipoteza lui Szymanski se referă la adecvarea unui hipercub ca topologie de rețea pentru schimbul de date. Ipoteza afirmă că, indiferent de modul în care se rearanjează vârfurile unui graf, există întotdeauna astfel de căi (dirijate) care leagă nodurile cu imaginile lor încât să nu treacă două căi care să leagă vârfuri diferite de-a lungul aceleiași muchii în aceeași direcție [8] .

Vezi și

Cicluri cubice conectate
Cubul Fibonacci
Grafic cub stivuit
Grafic cub înjumătățit

Note

↑ Mori. Câteva cicluri complete pe n-cubul // Proceedings of the American Mathematical Society. - Societatea Americană de Matematică, 1963. - V. 14 , nr. 4 . — S. 640–643 . - doi : 10.2307/2034292 . — . .
↑ Potrivirile perfecte se extind la ciclurile hamiltoniene în hipercuburi // Journal of Combinatorial Theory, Series B. - 2007. - Vol. 97 . — S. 1074–1076 . - doi : 10.1016/j.jctb.2007.02.007 . .
↑ Ruskey, F. și Savage, C. Potrivirile se extind la ciclurile hamiltoniene în hipercuburi Arhivat 6 mai 2021 la Wayback Machine pe Open Problem Garden. 2007.
↑ G. Ringel. ber drei kombinatorische Probleme am n-dimensionalen Wiirfel und Wiirfelgitter // Abh. Matematică. sere. Univ. Hamburg. - 1955. - T. 20 . - S. 10-19 .
↑ 1 2 Frank Harary, John P. Hayes, Horng-Jyh Wu. Un studiu al teoriei graficelor hipercubice // Calculatoare și matematică cu aplicații. - 1988. - T. 15 , nr. 4 . — S. 277–289 . - doi : 10.1016/0898-1221(88)90213-1 . .
↑ Y. Roichman. Despre numărul acromatic de hipercuburi // Journal of Combinatorial Theory, Seria B. - 2000. - Vol. 79 , nr. 2 . — S. 177–182 . - doi : 10.1006/jctb.2000.1955 . .
↑ Optimal Numberings and Isoperimetric Problems on Graphs, LH Harper, Journal of Combinatorial Theory , 1, 385-393, doi : 10.1016/S0021-9800(66)80059-5
↑ Ted H. Szymanski. Proc. Internat. Conf. privind procesarea paralelă. - Silver Spring, MD: IEEE Computer Society Press, 1989. - V. 1. - S. 103–110. .

Link -uri

F. Harary, JP Hayes, H.-J. Wu. Un studiu al teoriei graficelor hipercubice // Calculatoare și matematică cu aplicații . - 1988. - T. 15 , nr. 4 . — S. 277–289 . - doi : 10.1016/0898-1221(88)90213-1 . .