שאלה 4 29/6/06

שאלה 4 29/6/06

shiran (guest) 05 Feb 2012 16:33

היי,
אשמח אם תשתפו אותי בפתרון רשמי של סעיף א של השאלה הנל

ומדוע לא ניתן לפתור את סעיף ב ברשת 0-1 בעזרת דיניץ
ע"י חלוקת קודקודי ki למספר טבעי של קודקודים שהוא מייצג

Re: שאלה 4 29/6/06

adamsh 05 Feb 2012 17:32

היי שירן,

לגבי ב', הבעיה היא שהמשקלים של הקשתות הללו הם לאו דווקא קבועים.
יכול להיות למשל שחלק מהקיבולים הם m/100 או משהו כזה.
כך שפיצול קודקודים ישנה את הגודל של הגרף.

לגבי א', זו שאלה מתרגיל בית 5.
זה נובע ישירות מזה שבכל פאזה של דיניץ, אנו מוצאים מסלולים ארוכים ממש מהמסלולים שמצאנו בפאזה הקודמת.
למשל, אם שני הקודקודים נמצאים בצדדים שונים של הגרף, אז כל המסלולים ביניהם יהיו באורך אי זוגי.
לכן, במקרה הכי גרוע, בסיבוב הראשון יהיו מסלולים באורך 1, בסיבוב השני מסלולים באורך 3, 5, וכו'.

אדם