גרף תחרות

גרף תחרות

גרף תחרות בעל 4 צמתים
מספר צמתים	$n$
מספר קשתות	${n \choose 2}$

גרף תחרות (נקרא גם טורניר) הוא גרף מכוון כך שלכל שני קודקודים $\displaystyle u$ ו-$\displaystyle v$ קיימת בדיוק אחת מהקשתות $\displaystyle (u,v)$ ו-$\displaystyle (v,u)$. במילים אחרות גרף תחרות מתקבל על ידי הוספת כיוון יחיד לכל אחת מקשתות גרף שלם (לא מכוון). באופן טבעי גרף כזה מייצג ניצחון או הפסד בין כל 2 קודקודים. סכום דרגת היציאה והכניסה של כל קודקוד בגרף תחרות עם $\displaystyle n$ קודקודים הוא $\displaystyle n-1$.

מסלולים המילטונים בגרף תחרות

משפט שהוכח על ידי רדאי (Rédei) אומר כי בכל גרף תחרות יש מסלול המילטוני. ניתן להוכיח זאת באינדוקציה. בסיס האינדוקציה: נניח שבגרף יש 2 קודקודים, $\displaystyle v_{0},v_{1}$, אזי קיים מסלול אחד ביניהם.

הנחת האינדוקציה: אם קיימים $\displaystyle n$ קודקודים בגרף תחרות אזי יש בו מסלול המילטוני.

צעד האינדוקציה: יהי הגרף $\displaystyle T=(V,E)$ כך ש-$\displaystyle |V|=n+1$ גרף תחרות ונבחר קודקוד $\displaystyle v$ שדרגת היציאה שלו איננה 0. נתבונן בגרף ${\hat {T}}$ שמתקבל על ידי השמטת $\displaystyle v$. גם ${\hat {T}}$ הוא גרף תחרות ולפי הנחת האינדוקציה יש ב-${\hat {T}}$ מסלול המילטון. כלומר ניתן לסדר את כל n הקודקודים בשורה $v_{0},v_{1},\dots ,v_{n-1}$ כך שכל אחד מהם יופיע בה פעם אחת, והשורה מהווה מסלול פשוט מ-$v_{0}$ ל-$v_{n-1}$. עתה נוסיף חזרה את הקודקוד $\displaystyle v$ שהשמטנו. קיים $\displaystyle v_{i}$ מינימלי כך ש-$\displaystyle v$ מצביע אליו. אם $\displaystyle i=0$ נצרף את הקודקוד לפני $\displaystyle v_{0}$ ואז: ${v,v_{0},v_{1},\dots ,v_{n-1}}$ הוא מסלול המילטוני ב-$\displaystyle T$. אם $\displaystyle i>0$ אז מובטח לנו כי $\displaystyle v_{i-1}$ מצביע על $\displaystyle v$, אחרת נקבל סתירה למינימליות $\displaystyle i$. כעת נחבר את $\displaystyle v$ בין $\displaystyle v_{i-1}$ ל-$\displaystyle v_{i}$ ונקבל את המסלול ${v_{0},v_{1},\dots v_{i-1},v,v_{i},\dots v_{n-1}}$ אשר מהווה מסלול המילטוני בגרף $\displaystyle T$.

הוכחה זו אף מגדירה אלגוריתם למציאת מסלול המילטוני אשר זמן הריצה שלו הוא $\displaystyle n^{2}$. ידוע כי יש אלגוריתמים יעילים יותר, עם קשר הדוק לאלגוריתמי מיון, הדורשים בדיקה של $\displaystyle O(n\log n)$ קשתות בלבד.(ההוכחה למעלה קשורה למיון הכנסה).

גרף תחרות טרנזיטיבי

גרף תחרות טרנזיטיבי עם 8 צמתים

גרף תחרות נקרא טרנזיטיבי אם קיומה של קשת מ-$\displaystyle u$ ל-$\displaystyle v$ ומ-$\displaystyle v$ ל-$\displaystyle w$ גורר את קיומה של קשת מ-$\displaystyle u$ ל-$\displaystyle w$. ידוע כי התנאים הבאים שקולים לגרף תחרות $\displaystyle T$:

1. $\displaystyle T$ הוא טרנזיטיבי
2. אין ב-$\displaystyle T$ מעגלים מכוונים
3. אין ב-$\displaystyle T$ מעגל מכוון בגודל 3
4. קבוצת דרגות היציאה ב-$\displaystyle T$ היא {2,1,0,...,n − 1}
5. יש ב-$\displaystyle T$ רק מסלול המילטוני אחד

בכל גרף תחרות עם $\displaystyle n$ צמתים קיים תת-גרף תחרות טרנזיטיבי על $\displaystyle \log n$ צמתים.

ידוע גם כי בגרף תחרות אשר איננו טרנזיטיבי יש לפחות שלושה מסלולים המילטונים שונים ובכל גרף תחרות יש מספר אי זוגי של מסלולים המילטוניים.

סדרת הדרגות של גרף תחרות

יש תנאים פשוטים לאפשרות קיומו של גרף תחרות עם סדרת דרגות יציאה נתונות, כפי שהוכח על ידי לנדאו. תהא $(s_{1},s_{2},\cdots ,s_{n})$ סדרה מונוטונית לא יורדת. אז היא יכולה להוות סדרת דרגות יציאה של גרף תחרות עם צמתים אם ורק אם:

1. $0\leq s_{1}\leq s_{2}\leq \cdots \leq s_{n}$
2. $s_{1}+s_{2}+\cdots +s_{i}\geq {i \choose 2}$ עבור $n-1,\cdots ,2,1=i$
3. $s_{1}+s_{2}+\cdots +s_{n}={n \choose 2}$

נקרא לצומת מלך אם קים מסלול באורך 2 לכל היותר ממנו לכל צומת אחר. תכונה נוספת אשר מתקיימת בגרף תחרות היא קיומו של מלך. בפרט, כל הצמתים בעלי דרגת היציאה המקסימלית חייבים להיות מלכים. ידוע גם כי אם אין בגרף התחרות צומת שדרגתו $\displaystyle n-1$ ("קיסר") אז יש לפחות שלושה מלכים.

קישורים חיצוניים

• גרף תחרות, באתר MathWorld (באנגלית)
• תחרויות (תורת הגרפים), דף שער בספרייה הלאומית