“Kautz graph”的意思、由来-开放百科全书

词条

Kautz graph

释义

Properties
In computing
Notes

The Kautz graph is a

directed graph of degree and dimension , which has vertices labeled by all

possible strings of length which are composed of characters chosen from

an alphabet containing distinct

symbols, subject to the condition that adjacent characters in the

string cannot be equal ().

The Kautz graph has edges

It is natural to label each such edge of

as , giving a one-to-one correspondence

between edges of the Kautz graph

and vertices of the Kautz graph

Kautz graphs are closely related to De Bruijn graphs.

Properties

For a fixed degree and number of vertices , the Kautz graph has the smallest diameter of any possible directed graph with vertices and degree .
All Kautz graphs have Eulerian cycles. (An Eulerian cycle is one which visits each edge exactly once—This result follows because Kautz graphs have in-degree equal to out-degree for each node)
All Kautz graphs have a Hamiltonian cycle (This result follows from the correspondence described above between edges of the Kautz graph and vertices of the Kautz graph ; a Hamiltonian cycle on is given by an Eulerian cycle on )
A degree- Kautz graph has disjoint paths from any node to any other node .

In computing

The Kautz graph has been used as a network topology for connecting processors in high-performance computing^[1] and fault-tolerant computing^[2] applications: such a network is known as a Kautz network.

Notes

1. ^{{cite web | url=http://pl.atyp.us/wordpress/?p=1275 | title=The Kautz Graph | author=Darcy, Jeff | date=2007-12-31 | publisher=Canned Platypus}}
2. ^{{cite conference |first=Dongsheng |last=Li |author2=Xicheng Lu |author3=Jinshu Su |title=Graph-Theoretic Analysis of Kautz Topology and DHT Schemes |booktitle=Network and Parallel Computing: IFIP International Conference |pages=308–315 |publisher=NPC |date=2004 |location=Wuhan, China |url=https://books.google.com/books?id=DpDwhffRCjwC&pg=PA308&lpg=PA308&dq=kautz+graph&source=web&ots=QWy7s3YiHU&sig=KHsfzBYxBWdiNjZ4pn8YUoArB0A&hl=en |accessdate=2008-03-05 | isbn=3-540-23388-1 }}

2 : Parametric families of graphs|Directed graphs

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。