Grev Kautza

Kautz-grafen er en rettet graf af grad og dimension , som har toppunkter mærket med alle mulige længdestrenge , som er sammensat af tegn valgt fra et alfabet , der indeholder forskellige tegn med den betingelse, at tilstødende tegn ikke kan matche ( ). $K_{M}^{N+1}$ $M$ $N+1$ ${\displaystyle (M+1)M^{N))$ $s_{0}\cdots s_{N}$ $N+1$ $s_{i}$ $EN$ $M+1$ $s_{i}\neq s_{i+1}$

Kautz-grafen har kanter $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}\ i A\;s_{i}\neq s_{i+1}\}\,$

Det er naturligt at mærke hver sådan kant som , hvilket skaber en en-til-en overensstemmelse mellem kanterne på Kautz-grafen og hjørnerne på Kautz-grafen . $K_{M}^{N+1}$ $s_{0}s_{1}\cdots s_{N+1}$ $K_{M}^{N+1}$ $K_{M}^{N+2}$

Greverne af Kautz er nært beslægtede med greverne af de Bruijn .

Egenskaber

For en fast grad og antal knudepunkter har Kautz-grafen den mindste diameter for enhver rettet graf med knudepunkter og grad . $M$ $V=(M+1)M^{N}$ $V$ $M$
Alle Kautz-grafer har Euler-cyklusser . (En Euler-cyklus er en cyklus, der besøger hver kant nøjagtigt én gang - dette resultat følger af det faktum, at Kauz-grafer har en indegree lig med udgraden for hver node.)
Alle Kautz-grafer har en Hamilton-cyklus (dette resultat følger af den ovenfor beskrevne overensstemmelse mellem kanterne på Kautz-grafen og hjørnerne af Kautz-grafen . Hamilton-cyklussen på er givet af Euler-cyklussen på ). ${\displaystyle K_{M}^{N))$ $K_{M}^{N+1}$ $K_{M}^{N+1}$ ${\displaystyle K_{M}^{N))$
Kautz-gradgrafen har ikke-skærende stier fra enhver knude til enhver anden knude . $k$ $k$ $x$ $y$

I databehandling

Kautz-grafen er blevet brugt som en netværksteknologi til at forbinde processorer i højtydende databehandling [1] og fejltolerant databehandling [2] , sådanne netværk er kendt som Kautz-netværk .

Noter

↑ Darcy, 2007 .
↑ Li, Lu, Su, 2004 , s. 308-315.

Litteratur

Jeff Darcy. Kautz-grafen . — Næbdyr på dåse , 2007.
Dongsheng Li, Xicheng Lu, Jinshu Su. Network and Parallel Computing: IFIP International Conference . - Wuhan, Kina: NPC, 2004. - ISBN 3-540-23388-1 .