משחק עץ פורש

בתורת המשחקים, משחק עץ פורש (minimum cost spanning tree game) הוא משחק שיתופי שבו לכל קואליציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} c(S),S \end{align} } היא ההוצאה המינימלית הדרושה כדי לחבר את כל חברי ${\begin{aligned}S\end{aligned}}$ לקדקוד הראשית של העץ.

הגדרה

תהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}(N,V,E,v_{0},a,I)\end{align}} מערכת עץ פורש שבה:

• הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}N = \{1,2,...,n\}\end{align}} היא קבוצת שחקנים.
• הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}(V,E)\end{align}} הוא גרף סופי קשיר שבו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}V = \{v_{1}\,,v_{2}\,...,v_{n-1}\}\end{align}} היא קבוצת הקודקודים ו- ${\begin{aligned}E=\{e_{1}\,,e_{2}\,...,e_{n}\}\end{aligned}}$ היא קבוצת הקשתות.
• הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}v_{0}\in V\end{align}} הוא קדקוד הראשית, או המקור.
• הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}a:E\rightarrow R_{++}\end{align}} היא פונקציה המתאימה לכל קשת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}e \in E\end{align}} הוצאה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}a(e)\end{align}} גדולה מ- הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle {\begin{aligned}0\end{aligned}}} .
• הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}I:N\rightarrow V \setminus \{v_{0}\} \end{align}} היא פונקציה המתאימה לכל שחקן קדקוד שאינו המקור.

אוסף קשתות המחבר את חברי קואליציה כלשהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}S\end{align}} למקור, הוא אוסף המכיל לכל שחקן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} i \end{align}} ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} S \end{align}} , מסלול ${\begin{aligned}I(i)\end{aligned}}$ המוביל מהקדקוד למקור. ההוצאה של אוסף קשתות היא סכום ההוצאות של כל הקשתות באוסף.

תהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}S\end{align}} קואליציה ו- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}C\end{align}} קבוצת ההוצאות של כל אוספי הקשתות המחברים את חברי הקואליציה למקור.

נסמן ב- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}c(S)\end{align}} את ההוצאה המינימאלית מבין כל ההוצאות של האוספים המחברים את חברי ${\begin{aligned}S\end{aligned}}$ למקור.

משחק עץ פורש הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle {\begin{aligned}(N;c)\end{aligned}}} המתאים למערכת עץ פורש, הוא משחק שבו לכל קואליציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} c(S),S \end{align}} היא ההוצאה המינימלית הדרושה כדי לחבר את כל חברי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} S\end{align}} למקור.

אוסף (או אוספי) הקשתות שההוצאות להקמתו הן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}c(S)\end{align}} , הוא עץ ששורשו במקור. עץ זה נקרא עץ ההוצאות המינימליות של הקואליציה ${\begin{aligned}S\end{aligned}}$ ומסומן על ידי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}(V^S,E^S)\end{align}} .

דוגמה

שגיאה ביצירת תמונה ממוזערת:

משחק עץ פורש

נתבונן במערכת עץ פורש הכוללת קודקוד מקור ו-5 שחקנים, ושערכי הקשתות שלה הם:
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}E = \{e_{1}=1\,,e_{2}=3\,,e_{3}=4\,,e_{4}=3\,,e_{5}=1\,,e_{6}=1\,,e_{7}=1\,,e_{8}=1\,,e_{9}=3\}\end{align}}

ניקח את הקואליציה הכוללת את שחקן 2, שחקן 3, ושחקן 4.

עץ ההוצאות המינימלי של קואליציה זו הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}e_{1}\,,e_{6}\,,e_{7}\,,e_{8} \end{align}} וערכו הוא 4. במקרה זה, שחקן 1 הוא "נוסע חופשי": הוא זוכה בחיבור למקור למרות שאינו חבר בקואליציה.

תכונות נוספות

משחק עץ פורש מהווה דוגמה למשחק בו ניתן להוכיח (בתנאים מסוימים) שהליבה אינה ריקה, על ידי מציאת נקודה בליבה.

נתבונן למשל במקרה פרטי של מערכת עץ פורש בה הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}I\end{align}} היא חד חד ערכית ועל ,כלומר כל קודקוד משויך לשחקן אחד ויחיד.

במקרה זה, עץ ההוצאות המינימליות הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle {\begin{aligned}(V^{N},E^{N})\end{aligned}}} מכיל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} n \end{align}} קשתות, כאשר לכל שחקן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} i \end{align}} ניתן לשייך את הקשת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} e(i) \end{align}} - הקשת היוצאת ממנו לכיוון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} v_{0} \end{align}} .

ניתן להוכיח כי הווקטור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}x_{i} := a(e(i))\end{align}} נמצא בליבה של משחק העץ הפורש המתאים ולכן היא אינה ריקה.

דרך אחרת להראות שהליבה אינה ריקה, היא להוכיח שמשחק העץ הפורש הוא קמור. משחקי עץ פורש המוגדרים באופן דומה למשחק המופיע בדוגמה לעיל, הם קמורים ולכן הליבה שלהם אינה ריקה.

ראו גם

• מונחים בתורת המשחקים

לקריאה נוספת

• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, ירושלים: מאגנס, 2008, מסת"ב 9654932946