گراف کاتز

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

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

گراف کاتز $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}\in A\;s_{i}\neq s_{i+1}\}\,$

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

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

خصوصیات

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

محاسبات

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