איך מקשרים בין קבוצת הקודקודים הרלוונטים לרקחים

איך מקשרים בין קבוצת הקודקודים הרלוונטים לרקחים

Guy (guest) 07 Apr 2013 15:53

אני מבין את האלגוריתם הכללי שמוצא אם יש מסלול בין הרקחים הרלוונטים ( אלו שיש בהם קודקד אחד לפחות מקבוצה s)

אך מה שאני לא בטוח לגביו זה- אחרי שמצאנו רקחים כללים בגרף, איך אנו מקשרים בין קודקוד מסוים מקבוצה s לרקח שמתאים לו?

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

האם הקודקודים בקבוצה s מסומנים בצורה כלשהי בגרף G עצמו, ככה שבמעבר עליהם תוך כדי חיפוש DFS אנו יכולים לדעת שזה קודקוד רלוונטי ולזכור אותו כנציג של הרקח

בו אנו נמצאים?

אשמח להסבר.

תודה רבה.

Re: איך מקשרים בין קבוצת הקודקודים הרלוונטים לרקחים

Shai V 07 Apr 2013 19:42

הי,
אפשר לממש את זה בכמה דרכים, אבל בעקרון, כשבונים את הרק"חים - בונים גרף חדש (גרף העל) - ואפשר לקשר בין כל קודקוד בגרף העל לכל קודקוד ברק"ח שהוא מייצג. בנוסף, אין בעיה לסמן את הקודקודים בגרף, ולסמן את הרק"חים שצריך, ולסמן את הקשתות שצריך, ובקודקודים בגרף העל לשמור מצביעים לכל הקודקודים הרלוונטיים.
לזכור שכשיש לך זמן ריצה לינארי, אתה יכול לעשות כל מניפולציה שלוקחת זמן לינארי "בחינם". זאת אומרת שאם בא לך לשמור 30 העתקים של הגרף, ובכל אחד לתת לכל קודקוד 100 שדות בשביל לשמור דברים ועוד להוסיף $50|E|$ קשתות, זה בסדר.

שי