تورنمنت

به گراف کامل ساده جهت‌دار، تورنمنت می‌گویند. به عبارت دیگر بین هر دو راس آن دقیقا یک یال جهت دار وجود دارد. به گراف روبرو نگاه کنید.

شبیه سازی مسائل برد و باخت در بین گروهی که هر دو نفر باهم یک بار بازی کرده‌اند بهترین مثال برای درک این دسته از گراف هاست که نام تورنمنت از همین موضوع گرفته شده است. می‌گوییم $v$، $u$ رابرده ($u$ از $v$ باخته) اگر $v$ به $u$ یال جهت‌دار داشته باشد.

مسیر همیلتونی در گراف جهت دار، مسیری است که از یک راس شروع شده، در راستای جهت یال ها حرکت کرده، از تمام راس ها دقیقا یک بار عبور کرده و در نهایت در یک راس انتهایی به پایان برسد. مسیر همیلتونی مشابه دور همیلتنیست با این تفاوت که به راس شروع برنمی‌گردیم. یکی از مسیر‌های همیلتونی این تورنمنت با آبی مشخض شده‌است.

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

حکم را به صورت استقرایی ثابت می‌کنیم.

پایه: حکم مسئله برای تورمنت ۱ و ۲ راسی واضح است.

گام: فرض کنید مجموعه راس‌های تورنمنت ما $\{a_1,a_2,\dots,a_{n-1},v\}$ است. که برای زیر گرافی با رئوس $a_1$ تا $a_{n-1}$ مسیر همیلتونی وجود دارد. که می‌توان فرض کرد این مسیر از $a_1$ به ترتیب شروع شده تا $a_{n-1}$ ادامه دارد. مانند تصویر اگر $v$ از $a_1$ برده باشد مسیر ما بدین شکل می‌شود پس حالتی که $v$ از $a_1$ باخته است را در نظر می‌گیریم. حال اگر $v$ از $a_2$ را برده باشد باز مسیری به این شکل وجود دارد. پس تورمنت ما محدود به حالتی می‌شود که $v$، $a_1$ و $a_2$ را برده‌اند. حال در این حالت با همان استدلال می‌توان نتیجه گرفت در حالتی که $v$، $a_3$ را ببرد مسئله حل است. با همین روش ادامه می‌دهیم تنها حالتی که باقی می‌ماند این است که $v$ از همه رئوس برده باشد که باز مسیری به این شکل به وجود می‌آید.

یک تورنمنت تنها زمانی خاصیت تعدی دارد که به ازای هر ۳ رأس $b$ ،a و $c$ رابطه‌ی زیر همواره برقرار باشد:

اگر $a$ به $b$ و $b$ به $c$ یال جهت دار دارد آنگاه $a$ به $c$ یال جهت دار داشته‌باشد. به عبارت ریاضی:

و

تورنمنت با خاصیت تعدی معادل با تورمنتی که یکی از خاصیت های زیر را داشته باشد:

۱- تورمنتی که دور ندارد.

اثبات: اگر در فرض ویژگی تعدی به جای آنکه $c$ به $a$ یال داشته باشد، $a$ به $c$ یال داشته باشد، یک دور به طول سه خواهیم داشت. پس می‌توان گفت ویژگی تعدی معادل است با نداشتن دور به طول سه: «نداشتن دور به طول سه $ \Leftrightarrow $ ویژگی تعدی» پس می‌توان نتیجه گرفت:

نداشتن دور $\Leftarrow$ نداشتن دور به طول سه $\Leftarrow$ ویژگی تعدی

برای اثبات عکس رابطه بالا و کامل کردن اثبات باید «نداشتن دور به طول سه $\Leftarrow$ نداشتن دور» را ثابت کنیم.

فرض خلف: فرض کنید دوری به طول $k$ داریم ولی دور به طول ۳ نداریم، k باید از ۳ بیشتر باشد در غیر این صورت همینجا به تناقض رسیدیم. فرض کنید راس های این دور $a_1$ تا $a_k$ هستند و $a_1$ به $a_2$ یال جهت‌دار دارد و $a_2$ به $a_3$ و … و $a_k$ به $a_1$ یال جهت دار دارد. می‌دانیم $a_1$ به $a_3$ یا $a_3$ به $a_1$ یال جهت دار دارد. اگر $a_3$ به $a_1$ یال جهت دار داشته باشد، دور ۳ تایی $a_1$، $a_2$، $a_3$ به وجود می‌اید، پس $a_1$ به $a_3$ یال جهت دار دارد. همین استدلال را برای یال بین $a_1$ و $a_4$ و دور ۳ تایی $a_1$، $a_3$، $a_4$ کرد، و همین گونه این استدلال را تا $a_{k-1}$ ادامه داد. پس $a_1$ باید به $a_{k-1}$ یال جهت دار داشته باشد ولی در این صورت دور ۳ تایی $a_1$، $a_{k-1}$، $a_k$ به وجود می‌آید که فرض خلف اولیه را رد و اثبات را کامل می‌کند.

۲ – تورنمتی که قابلیت مرتب‌سازی توپولوژیک را دارد.

گراف جهت دار‌ی که دور ندارد فابلیت مرتب‌سازی توپولوژیک دارد و برعکس. برای اثبات مراجعه کنید به صفحه الگوریتم مرتب‌سازی توپولوژیک

۳- تورنمنتی که مجموعه‌ی درجه‌ خروجی راس‌هایش $\{0,1,2,\dots,n-1\}$ است که $n$ تعداد راس هاست. یعنی درجه خروجی تمام راس متفاوت است و همه اعداد ممکن برای درجه خروجی را داریم.

اثبات: بعد ار مرتب کردن راس ها به صورت توپولوژیک راس اول تمام راس های بعد از خودش را برده(به آنها یال جهت‌دار دارد) پس درجه خروجی‌اش $n-1$ است، راس دوم هم تمام راس های بعد از خودش را برده پس درجه خروجیش $n-2$ است و به همین ترتیب راس $k$ ام درجه خروجی اش $n-k$ است. پس مجموعه درجه خروجی راس ها شامل همه اعداد ۰ تا $n-1$ هست. حال فرض کنید تورنمنتی با این مجموعه درجه خروجی داشته باشیم. می‌توان فرض کرد $a_i$، $i-1$ یال خروجی دارد و $n \ge i \ge 1$. $a_n$ همه را برده پس در مرتب سازی توپولوژیک باید اول قرار بگیرد. $a_{n-1}$ از $a_n$ باخته پس بقیه را باید برده باشد. پس می‌توان آنرا بعد از $a_n$ قرار داد. $a_{n-2}$ از $a_n$ و $a_{n-1}$ باخته پس بقیه را باید برده باشد پس می‌توان در مرتب سازی آنرا بعد از این دو قرار داد به همین سبک بقیه رئوس را می‌توان مرتب کرد، پس می‌توان یک مرتب سازی توپولوژیک ارائه داد. پس گراف ویژگی تعدی دارد.

۴- تورنمنتی که دقیقاً یک مسیر همیلتونی دارد

تورمنت با ویژگی تعدی را می‌توان توپولوژیک مرتب کرد پس این تورمنت را به صورت توپولوژیک مرتب می‌کنیم. حال مسیر همیلتونی تنها در جهت مرتب شده می‌تواند پیش رود، پس تنها حالت ممکن این است که از راس اول شروع کند و به ترتیب راس ها را به ترتیب مرتب شده طی کند. اگر تورنمنت دقیقا یک مسیر همیلتونی داشته‌باشد. فرض کنید راس های این مسیر به ترتیب $a_1$، $a_2$، $a_3$، … ، $a_n$ است.(یعنی $a_1$، $a_2$ را برده، $a_2$، $a_3$ برده است و …) می‌خواهیم ثابت کنیم همین مسیر، به صورت توپولوژیک مرتب شده است. فرض خلف: فرض کنید راس $i$ وجود دارد که حداقل از یکی از راس های بعد از خود( مثلا راس $a_j$ که $j>i$) باخته است. بین تمام $i$ ها با این خاصیت کوچکترین ان را در نظر بگیرید. می‌خواهیم نشان دهیم یک مسیر همیلتونی دیگر به جز $a_1$، $a_2$، $a_3$، … ، $a_n$ وجود دارد. تمام راس های بعد از $a_i$ (تمام $a_k$ ها که $k>i$) را به دو دسته تقسیم کنید. دسته‌ی اول رئوسی که از $a_i$ باخته‌اند(که شامل $a_{i+1}$ است)، دسته‌ی دوم رئوسی که $a_i$ را برده‌اند(بر طبق فرض شامل حداقل یک راس است مثلا $a_j$). حال می‌دانیم هر کدام از این دسته ها یک زیر گرافند که خود تورنمت هستند پس دارای یک مسیر همیلتونی هستند. راس انتهایی مسیر همیلتونی دسته‌ی دوم از $a_i$ برده و $a_i$ راس ابتدایی مسیر همیلتونی دسته‌ی اول را برده، پس مسیر همیلتونی دسته‌ی دوم، سپس راس $a_i$ و بعد مسیر همیلتونی دسته‌ی اول خود یک مسیر همیلتونی برای زیر گراف رئوس $a_i$ تا $a_n$ است. حال اگر راس های $a_1$ تا $a_{i-1}$ را به ابتدای این مسیر اضافه کنیم، یک مسیر همیلتونی برای کل تورنمنت خواهیم داشت.($a_{i-1}$ تمام رئوس بعد از خود را برده چون فرض کردیم $i$ کوچکنرین راس است که این خاصیت را ندارد پس چنین مسیری تشکیل خواهد شد). این مسیر به وضوح با مسیر همیلتونی اولیه متفاوت است زیرا $a_i$ در این مسیر بعد از $a_j$ آمده. که با فرض اولیه در تناقض است که اثبات حکم را نتیجه می‌دهد.

مثال: فرض کنید راس $v$، بیشترین درجه خروجی را در تورنمنت دارد، ثابت کنید از $v$ به هر راس دیگر یک مسیر به طول ۱ یا ۲ وجود دارد.(توجه کنید که ممکن است چند راس بیشترین درجه خروجی را داشته باشند که $v$ یکی از این رئوس است)

• تورنمنت - ویکی‌پدیا
• تورنمنت - دانشکده ریاضی دانشگاه آریزونا