מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/חיפוש רוחבי/תרגילים/"חיפוש רוחבי" עם שק במקום תור/תשובה v2

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

הדפסה לפי הסדר[עריכה]

הטענה איננה נכונה. קל למצוא דוגמאות נגדיות.



דוגמה:

נניח שהגרף הוא המתואר בתרשים הבא.

בעיית החיפוש הרוחבי.
בעיית החיפוש הרוחבי.

בגרף זה, סדר ההדפסות יכול להיות (משמאל לימין): .


עכשיו תורכם:

וודא שהנך מסוגל להראות סידרה אפשרית של תוצאות Delete שיביאו לתוצאה האמורה.


הדפסת כל הצמתים פעם יחידה[עריכה]

הטענה נכונה.


הוכחה: שורה 11 מבטיחה שכל צומת לא יודפס יותר מפעם יחידה, ולכן נותר להבטיח שכל צומת יודפס לפחות פעם אחת.

נוכיח שכל צומת מודפס ומוכנס לשק במהלך הריצה. ההוכחה היא באינדוקציה על , מרחק הצומת מ.

(בסיס האינדוקציה) עבור הטענה בוודאי נכונה. יש רק צומת אחד שמרחקו מ הוא 0, עצמו, ו מודפס ב5 ומוכנס לשק ב7.

(מעבר האינדוקציה) נניח שהטענה נכונה לכל צומת שמרחקו מ הוא לכל היותר (לא כולל) . נתבונן כעת בצומת כלשהו שמרחקו מ הוא . אם כך, בהכרח קיים צומת כך שיש מסלול מ ל באורך , ו שכן של . מהנחת האינדוקציה, מתישהו יודפס ויוכנס לשק. שורה 9, לכן, מבטיחה גם ש מתשיהו יוצא מהשק. הלולאה 10-14 עוברת על כל שכני , ובפרט . האפשרות היחידה לפיה 12 לא תדפיס את היא ש11 נכשלה. אם 11 נכשלה, אבל, אז בהכרח כבר הודפסה והוכנסה לתור (רק שורה 13 יכולה לקבוע את הערך בVisited לTrue). לכן, בכל מקרה, בהכרח מודפסת ומוכנסת לתור.