מבחן 12.7.07 - שאלה 3
Netanel (guest) 07 Feb 2012 17:39
היי,
בשאלה אנחנו מתבקשים לחשב את משקל המסלול המינימאלי מצומת s לכל צומת v כך שמספר הקשתות הוא זוגי.
הגרף הוא לא מכוון, לכל קשת יש משקל כלשהו, חיובי או שלילי, ואין בגרף מעגלים שליליים.
חשבתי לפצל כל קודקוד לשני צמתים, אחד זוגי אחד אי-זוגי, ככה שעבור קשת מקורית בגרף תהיה קשת ממופע אי-זוגי לזוגי, וממופע זוגי לאי-זוגי.
ואז לנסות ולמצוא את המסלולים מ-s even אל כל צומת ממופע זוגי, נניח בעזרת בלמן-פורד.
הבעיה היא שהגרף לא מכוון, וכיוון שלו יכול ליצור מעגלים שליליים…. יש אפשרות להתחמק מזה?
תודה רבה!