שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 2022 - מסלולים קצרים

נתון גרף מכוון ומשוקלל $G=(V,E)$ עם קדקוד מוצא $s$ ומשקלים $w(e)$ (חלקם עשויים להיות שליליים). ידוע שאין ב-$G$ מעגלים שליליים, ולכן קיים עץ מסלולים מזעריים (עמ"מ) $T$ מ-$s$. הגדרה: הגרף $G$ ייקרא **"מיוחד"** אם לכל קדקוד $v \neq s$ קיימת לפחות צלע שלילית אחת ש**יוצאת** מ-$v$. הכריעו את נכונותן של הטענות הבאות: א. "לכל גרף מיוחד יש עמ"מ $T$ שכולל לפחות צלע שלילית אחת." ב. "קיימת סדרה אינסופית של גרפים מיוחדים (שמספר הקדקודים בהם הולך וגדל), ועבור כל גרף מיוחד בסדרה מתקיים שכל עמ"מ $T$ כולל רק צלעות חיוביות.\"

רמז: שימו לב להבדל בין צלעות ה**יוצאות** מקדקוד (עליהן מדברת ההגדרה "מיוחד") לבין צלעות ה**נכנסות** אליו (מהן בנוי עץ המסלולים המזעריים). האם אפשר "לצבוע" כל קדקוד כמיוחד באמצעות צלע יוצאת שאינה משתתפת באף מסלול פשוט?

פתרון: **רעיון מרכזי.** התכונה "מיוחד" נוגעת לצלעות ה**יוצאות** מכל קדקוד, בעוד שעץ המסלולים המזעריים בנוי מצלעות ה**נכנסות** לכל קדקוד (צלע ההורה במסלול מ-$s$). לכן צלע שלילית יוצאת אינה חייבת להשתתף בעמ"מ. **חלק א — אינו נכון (הפרכה).** נגדיר גרף $G_n$ באופן הבא: - הקדקודים הם $v_1,v_2,\dots,v_n$ כאשר $s=v_1$; - צלעות "שדרה" חיוביות: $(v_1,v_2),(v_2,v_3),\dots,(v_{n-1},v_n)$, כולן במשקל $+1$; - לכל קדקוד $v_i$ עם $i\ge 2$ צלע-עצמית $(v_i,v_i)$ במשקל $-1$. הגרף "מיוחד", שכן לכל $v\neq s$ יש צלע יוצאת שלילית — הצלע-העצמית שלו. אך עץ המסלולים המזעריים היחיד מ-$s$ הוא בדיוק המסלול $v_1\to v_2\to\cdots\to v_n$ שכל צלעותיו $+1$: מרחקים מוגדרים על **מסלולים פשוטים**, וצלע-עצמית לעולם אינה משתתפת במסלול פשוט, ולכן אינה נכללת בעמ"מ. מכאן שקיים גרף מיוחד שכל עמ"מ שלו כולל רק צלעות חיוביות — הטענה מופרכת. $\blacksquare$ **חלק ב — נכון.** אותה משפחה $\{G_n\}_{n\ge 1}$ מהווה סדרה אינסופית: מספר הקדקודים $n$ גדֵל ללא חסם, כל איבריה גרפים מיוחדים, ולכל אחד מהם עץ המסלולים המזעריים היחיד (שדרת ה-$+1$) כולל רק צלעות חיוביות. $\blacksquare$