گراف کاتز

گراف کاتز یا  یک گراف جهت‌دار از مرتبهٔ  و بُعد  است که دارای  راس است که این راس‌ها به وسیلهٔ تمام رشته‌های ممکن  با طول  که از کارکترهای  از الفبای  که شامل  نماد(حرف) مجزا است برچسب گذاری شده‌اند و در این برچسب گذاری هیچ دو حرف مجاوری برابر نیستند().

گراف کاتز  شامل  یال است

معمول است که هر یال از  را با  برچسب گذاری می‌کنند، که این کار یک نگاشت دوسویی بین یال‌های گراف کاتز  و راس‌های گراف کاتز  را نتیجه می‌دهد.

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

خصوصیات 
 برای یک درجهٔ ثابت  و تعداد راس‌های ، گراف کاتز، کوچکترین فاصله را با هر گراف جهت دار ممکن با  راس و  یال دارد.
 همهٔ گراف‌های کاتز دارای دور اویلری هستند. (دور اویلری دوری است که تمام یال‌ها را دقیقاً یک بار پیمایش می‌کند-- این نتیجه به این دلیل حاصل می‌شود که در گراف‌های کاتز درجهٔ ورودی هر راس با درجهٔ خروجی آن راس برابر است)
 تمام گراف‌های کاتز، دارای دور همیلتنی هستند. (این نتیجه از نگاشت دوسویی که بین یال‌های گراف کاتز  و راس‌های گراف کاتز  تعریف شد حاصل می‌شود)
 یک گراف کاتز درجهٔ  دارای  مسیر مجزا از هر راس  به راس دیگر  است.

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

منابع 

خانواده‌های پارامتری گراف‌ها
گراف‌های جهت‌دار