Contele Kautza

Graficul Kautz este un grafic direcționat de grad și dimensiune , care are vârfuri etichetate cu toate șirurile posibile de lungime , care sunt compuse din caractere alese dintr-un alfabet care conține diferite caractere cu condiția ca caracterele adiacente să nu se potrivească ( ). $K_{M}^{N+1}$ $M$ $N+1$ $(M+1)M^{N)$ $s_{0}\cdots s_{N}$ $N+1$ $si}$ $A$ $M+1$ $s_{i}\neq s_{i+1}$

Graficul Kautz are muchii $K_{M}^{N+1}$ $(M+1)M^{N+1}$

$\{(s_{0}s_{1}\cdots s_{N},s_{1}s_{2}\cdots s_{N}s_{N+1})|\;s_{i}\ în A\;s_{i}\neq s_{i+1}\}\,$

Este firesc să etichetați fiecare muchie ca , creând o corespondență unu-la-unu între muchiile grafului Kautz și vârfurile grafului Kautz . $K_{M}^{N+1}$ $s_{0}s_{1}\cdots s_{N+1}$ $K_{M}^{N+1}$ $K_{M}^{N+2}$

Conții de Kautz sunt strâns legați de conții de Bruijn .

Proprietăți

Pentru un grad și un număr fix de vârfuri , graficul Kautz are cel mai mic diametru pentru orice grafic direcționat cu vârfuri și grad . $M$ $V=(M+1)M^{N}$ $V$ $M$
Toate graficele Kautz au cicluri Euler . (Un ciclu Euler este un ciclu care vizitează fiecare muchie exact o dată - acest rezultat rezultă din faptul că graficele Kauz au un grad egal cu gradul exterior pentru fiecare nod.)
Toate graficele Kautz au un ciclu hamiltonian (Acest rezultat rezultă din corespondența descrisă mai sus dintre muchiile grafului Kautz și vârfurile grafului Kautz . Ciclul hamiltonian on este dat de ciclul Euler on ). $K_{M}^{N)$ $K_{M}^{N+1}$ $K_{M}^{N+1}$ $K_{M}^{N)$
Graficul gradului Kautz are căi care nu se intersectează de la orice nod la orice alt nod . $k$ $k$ $X$ $y$

În prelucrarea datelor

Graficul Kautz a fost folosit ca tehnologie de rețea pentru conectarea procesoarelor în calculul de înaltă performanță [1] și calculul tolerant la erori [2] , astfel de rețele fiind cunoscute ca rețele Kautz .

Note

↑ Darcy, 2007 .
↑ Li, Lu, Su, 2004 , p. 308–315.

Literatură

Jeff Darcy. Graficul Kautz . - Ornitorinci în conserve , 2007.
Dongsheng Li, Xicheng Lu, Jinshu Su. Network and Parallel Computing: Conferința internațională IFIP . - Wuhan, China: NPC, 2004. - ISBN 3-540-23388-1 .