גרף תחרות

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
גרף תחרות
4-tournament.svg
גרף תחרות בעל 4 צמתים
מספר צמתים n
מספר קשתות {n \choose 2}

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

מסלולים המילטונים בגרף תחרות[עריכת קוד מקור | עריכה]

משפט שהוכח על ידי רדאי (Rédei) אומר כי בכל גרף תחרות יש מסלול המילטוני,‏[1]. ניתן להוכיח זאת באינדוקציה. בסיס האינדוקציה: נניח שבגרף יש 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 צמתים.

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

סדרת הדרגות של גרף תחרות[עריכת קוד מקור | עריכה]

יש תנאי פשוטים לאפשרות קיומו של גרף תחרות עם סדרת דרגות יציאה נתונות, כפי שהוכח על ידי לנדאו‏[3]. תהא (s_1, s_2, \cdots, s_n) סדרה מונוטונית לא יורדת. אז היא יכולה להוות סדרת דרגות יציאה של גרף תחרות עם צמתים אם ורק אם:

  1. 0 \le s_1 \le s_2 \le \cdots \le s_n
  2. s_1 + s_2 + \cdots + s_i \ge {i \choose 2} עבור n-1 ,\cdots,2 ,1=i
  3. s_1 + s_2 + \cdots + s_n = {n \choose 2}

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

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Rédei, László (1934), "Ein kombinatorischer Satz", Acta Litteraria Szeged 7: 39–43 
  2. ^ Szele, T. "Kombinatorische Untersuchungen über den gerichteten vollständigen Graphen." Mat. Fiz. Lapok 50, 223-256, 1943
  3. ^ H.G. Landau, On dominance relations and the structure of animal societies, III: the condition for a score structure, Bull. Math. Biophys. 15 (1953), pp. 143–148.
  4. ^ J.W. Moon, Solution to problem 463, Math. Mag. 35 (1962), p. 189.