گراف کاتز

یک نمونه از K. گرافی با M=2. در سمت چپ N=1. در سمت راست N=2. یال‌های گراف سمت چپ نشان دهندهٔ راس‌های گراف سمت راست هستند. به خاطر داشته باشید که گراف سمت راست 3 یال کم دارد.

گراف کاتز یا ${\displaystyle K_{M}^{N+1}}$ یک گراف جهت‌دار از مرتبهٔ ${\displaystyle M}$ و بُعد ${\displaystyle N+1}$ است که دارای ${\displaystyle (M+1)M^{N}}$ راس است که این راس‌ها به وسیلهٔ تمام رشته‌های ممکن ${\displaystyle s_{0}\cdots s_{N}}$ با طول ${\displaystyle N+1}$ که از کارکترهای ${\displaystyle s_{i}}$ از الفبای ${\displaystyle A}$ که شامل ${\displaystyle M+1}$ نماد(حرف) مجزا است برچسب گذاری شده‌اند و در این برچسب گذاری هیچ دو حرف مجاوری برابر نیستند(${\displaystyle s_{i}\neq s_{i+1}}$).

گراف کاتز ${\displaystyle K_{M}^{N+1}}$ شامل ${\displaystyle (M+1)M^{N+1}}$ یال است

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

معمول است که هر یال از ${\displaystyle K_{M}^{N+1}}$ را با ${\displaystyle s_{0}s_{1}\cdots s_{N+1}}$ برچسب گذاری می‌کنند، که این کار یک نگاشت دوسویی بین یال‌های گراف کاتز ${\displaystyle K_{M}^{N+1}}$ و راس‌های گراف کاتز ${\displaystyle K_{M}^{N+2}}$ را نتیجه می‌دهد.

کراف کاتز به‌طور بسیار نزدیکی به گراف دی براین مربوط است.

خصوصیات

• برای یک درجهٔ ثابت ${\displaystyle M}$ و تعداد راس‌های ${\displaystyle V=(M+1)M^{N}}$، گراف کاتز، کوچکترین فاصله را با هر گراف جهت دار ممکن با ${\displaystyle V}$ راس و ${\displaystyle M}$ یال دارد.
• همهٔ گراف‌های کاتز دارای دور اویلری هستند. (دور اویلری دوری است که تمام یال‌ها را دقیقاً یک بار پیمایش می‌کند-- این نتیجه به این دلیل حاصل می‌شود که در گراف‌های کاتز درجهٔ ورودی هر راس با درجهٔ خروجی آن راس برابر است)
• تمام گراف‌های کاتز، دارای دور همیلتنی هستند. (این نتیجه از نگاشت دوسویی که بین یال‌های گراف کاتز ${\displaystyle K_{M}^{N}}$ و راس‌های گراف کاتز ${\displaystyle K_{M}^{N+1}}$ تعریف شد حاصل می‌شود)
• یک گراف کاتز درجهٔ ${\displaystyle k}$ دارای ${\displaystyle k}$ مسیر مجزا از هر راس ${\displaystyle x}$ به راس دیگر ${\displaystyle y}$ است.

محاسبات

گراف کاتز به عنوان یک ساختار شبکه برای وصل کردن پردازشگرها در محاسبات بسیار سریع^[۱] و محاسبات مقاوم در برابر خطا^[۲]، استفاده شده‌است. کاربرد: چنین شبکه‌هایی به عنوان شبکه کاتز شناخته می‌شوند.

منابع

1. Darcy, Jeff (2007-12-31). "The Kautz Graph". Canned Platypus. {{cite web}}: External link in |publisher= (help)
2. Li, Dongsheng (2004). "Graph-Theoretic Analysis of Kautz Topology and DHT Schemes". Network and Parallel Computing: IFIP International Conference. Wuhan, China: NPC. pp. 308–315. ISBN 3-540-23388-1. Retrieved 2008-03-05. {{cite conference}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)