تورنومنت¶

تعریف 3.2.2 (شاه)¶

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

قضیه 3.2.3¶

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

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

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

تعریف 3.2.4(مسیر همیلتونی در گراف جهت‌دار)¶

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

قضیه 3.2.5¶

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

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

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