تورنومنت
=============================================================================================

**تعریف 3.2.1 (تورنمنت)**
----------------------------------------------------------------------
تورنمنت، گراف ساده و کاملی است که یال‌های آن جهت‌دار شده‌اند (شکل 1 تورنمنتی با 5 راس می‌باشد).

.. figure:: /_static/tournament_1.png
   :width: 50%
   :align: left
   :alt: اگه اینترنت یارو آشغال باشه این میاد

یک تورنمنت 
:math:`n`
راسی می‌تواند مدلی برای مسابقات بین 
:math:`n`
تیم باشد به طوری که از راس 1 به راس 2 یال جهت‌دار است اگر و تنها اگر تیم 1 از تیم 2 برده باشد (مانند شکل 1).

شاه در تورنمنت‌ها
----------------------------------------------------------------------

**تعریف 3.2.2 (شاه)**
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
شاه، راسی درتورنمنت است که به تمام راس‌های تورنمنت مسیری جهت‌دار به طول حداکثر 2 دارد. به عنوان مثال راس 3، یک شاه در شکل 1 می‌باشد.

**قضیه 3.2.3**
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
**صورت قضیه :** هر تورنمنت حداقل یک شاه دارد.

**اثبات قضیه :** فرض کنید 
:math:`v`
راسی با درجه خروجی 
:math:`\Delta^{+}`
در تورنمنت باشد، یعنی راسی باشد که بیشنیه درجه خروجی را دارد. اگر راسی مانند 
:math:`u`
وجود داشته‌باشد که نتوان از 
:math:`v`
به آن با مسیری با طول حداکثر 2 برسیم، در این صورت 
:math:`u`
باید به 
:math:`v`
و تمام راسی‌های مانند 
:math:`w`
که 
:math:`(v,w) \in E`
، یال جهت‌دار داشته‌باشد (شکل 2) که در این صورت 
:math:`d^{+}(u) \geq \Delta^{+}+1`
که با بیشینه بودن درجه خروجی 
:math:`v`
در تناقض است. پس درنتیجه راسی وجود ندارد که از 
:math:`v`
نتوان با حداکثر دو یال به آن رسید  و 
:math:`v`
، شاه است.

.. figure:: /_static/tournament_2.png
   :width: 50%
   :align: left
   :alt: اگه اینترنت یارو آشغال باشه این میاد

قضیه 3.2.3 مانند این می‌باشد که به عنوان مثال در یک تورنمنت مسابقات، فردی مانند 
:math:`v`
وجود دارد که به ازای هر نفر مانند 
:math:`u`
یا آن را برده است یا شخصی را برده که 
:math:`u`
را برده است.

مسیر همیلتونی در تورنمنت‌
----------------------------------------------------------------------

**تعریف 3.2.4(مسیر همیلتونی در گراف جهت‌دار)**
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
یک مسیر همیلتونی در گراف جهت‌دار، مسیر جهت‌داری است که از تمام راس‌ها بگذرد.

**قضیه 3.2.5**
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
**صورت قضیه :** هر تورنمنت دارای حداقل یک مسیر همیلتونی است.

**اثبات قضیه :** فرض کنید راس‌های 
:math:`a_1`
تا 
:math:`a_k`
بلندترین مسیر جهت‌دار در تورنمنت را تشکیل دهند (شکل 3).

.. figure:: /_static/tournament_3.png
   :width: 50%
   :align: left
   :alt: اگه اینترنت یارو آشغال باشه این میاد

اگر 
:math:`k = n`
که حکم اثبات می‌شود، در غیر این صورت راسی مانند 
:math:`v`
وجود دارد که در این مسیر نمی‌باشد. از 
:math:`v`
به 
:math:`a_1`
و از 
:math:`a_k`
به 
:math:`v`
نمی‌تواند یال جهت‌دار باشد (چرا؟)، پس فرض کنید 
:math:`a_i`
راسی با کوچک‌ترین 
:math:`i`
بین تمام راس‌ها از 
:math:`a_1`
تا 
:math:`a_k`
باشد که 
:math:`v`
به آن‌ها یال دارد. در این صورت راس‌های
:math:`a_1,...,a_{i-1},v,a_i,...,a_k`
مسیری با طول 
:math:`k+1`
تشکیل می‌دهند، در صورتی که طول بلندترین مسیر برابر
:math:`k`
می‌باشد. در نتیجه 
:math:`k = n`
و 
:math:`a_1`
تا 
:math:`a_k`
تشکیل یک مسیر همیلتونی می‌دهند.