گراف کاتز

یک نمونه از 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\ne 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\ne 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$ است.

محاسبات

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