מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/מסלולים זולים לכלל הזוגות/תרגילים/זיהוי ארביטראג'/תשובה

את התשובה נפריד לשני חלקים: זיהוי מעגלים שליליים, ומציאת ארביטראז'.

זיהוי מעגלים שליליים

כידוע, אם יש מעגל שלילי בגרף, המושג מסלול זול ביותר איננו כלל מוגדר (אין מסלול סופי שהוא הזול ביותר). בפרט, אלגוריתם Floyd-Warshall לא יחזיר את התשובה הנכונה.

עם זאת, קל לחזור על ההוכחה של אלגוריתם Floyd-Warshall ולהווכח בנכונות הטענה הבאה. אם יש מעגל שלילי, האלגוריתם יחזיר מטריצה שבה יש לפחות מספר שלילי אחד באלכסון המטריצה (מעגל שלילי פירושו שאפשר להגיע מצומת לעצמו במחיר קטן מ0).

מציאת ארביטראז'

נבנה גרף חדש שבו הצמתים מתאימים למטבעות השונים, והקשתות מתארות המרות בין המטבעות. אם אפשר להמיר מטבע אחד למטבע שני ביחס $\displaystyle p$, אז נייחס מחיר $\displaystyle \log(1/p)$ לקשת. נשים לב שאם יש ארביטראז', אז קיימת סדרת המרות המקיימת $\displaystyle p_{1}\cdot p_{2}\cdots p_{k}>1$. תנאי זה שקול לתנאי $\displaystyle \log \left(1/p_{1}\right)+\log \left(1/p_{2}\right)+\cdots +\log \left(1/p_{k}\right)=\log \left(1/(p_{1}\cdot p_{2}\cdots p_{k})\right)<\log(1)=0$. התנאי לארביטראז' בטבלה, לכן, שקול לתנאי למעגל שלילי בגרף החדש.