گراف کامل جهت دار (Complete Directed Graph / Tournament)، در ریاضیات (Mathematics)
انواع گراف کامل (Complete Graph) را در آموزش زیر شرح دادیم :
گراف کامل جهت دار (Complete Directed Graph / Tournament) :
در این نوع گراف، به هر یال بین دو رأس، یک جهت (Direction) اختصاص داده می شود. به بیان دقیق تر، یک گراف کامل جهت دار یا تورنمنت (Tournament) از یک گراف کامل ساده
\[ K_n \]با جهت دار کردن هر یک از یال های آن به دست می آید. یعنی برای هر جفت رأس مجزا مانند
\[ u \]و
\[ v \]، دقیقا یکی از دو یال جهت دار
\[ u \to v \]یا
\[ v \to u \]وجود دارد. این گراف ها برای مدل سازی مسابقات دوره ای (Round-robin) در ورزش ها بسیار مناسب هستند، جایی که هر بازیکن یا تیم دقیقا یک بار با دیگران مسابقه می دهد و برنده مشخص می شود.
خواص این گراف ها بسیار جالب و مورد مطالعه قرار گرفته است. به عنوان مثال، یک قضیه معروف بیان می کند که هر تورنمنتی شامل یک مسیر همیلتونی (Hamiltonian Path) است، یعنی مسیری که از تمام رئوس دقیقا یک بار عبور می کند. همچنین، مفهوم "پادشاه" (King) در تورنمنت ها تعریف می شود: رأسی که بتوان با یک مسیر با حداکثر طول دو به هر رأس دیگر رسید. بررسی های گسترده ای روی ساختارهای درونی و خواص جبری این گراف ها انجام شده است. تعداد کل تورنمنت های ممکن روی
\[ n \]رأس برابر است با:
\[ 2^{\binom{n}{2}} \]چرا که برای هر یک از
\[ \binom{n}{2} \]جفت رأس، دو انتخاب برای جهت دار کردن یال وجود دارد.
