רכיב קשיר היטב
מתוך ויקיפדיה, האנציקלופדיה החופשית
בתורת הגרפים, גרף מכוון נקרא קשיר היטב אם קיים מסלול מכל צומת שבו אל כל צומת אחרת. עבור גרף מכוון כללי, ניתן תמיד לפרק את הגרף לרכיבים קשירים היטב - תת גרפים מקסימליים של הגרף המקורי, שכל אחד מהם הוא גרף קשיר היטב בפני עצמו. פירוק זה מהווה חלוקה של הגרף למחלקות זרות - שני רכיבים שונים לא יכולים להכיל צומת משותף. יתר על כן, הגרף שכל צומת בו מייצג אחד מהרכיבים הקשירים היטב, ויש קשת מכוונת בין שני צמתים אם ורק אם יש קשת בין הרכיבים בגרף המקורי, הוא גרף מכוון חסר מעגלים (DAG).
לפירוק גרף לרכיבים קשירים היטב יש חשיבות רבה לעתים - ישנם אלגוריתמים שמתבססים על ההנחה שהגרף עליו הם פועלים הוא קשיר היטב, ולכן כדי להפעיל אותם על גרף כללי מפרקים אותו לרכיבים קשירים היטב, מפעילים את האלגוריתם על כל רכיב בנפרד, ואחר כך מאחדים את התוצאות.
[עריכה] אלגוריתם למציאת רכיבים קשירים היטב
קיים אלגוריתם פשוט יחסית למציאת הרכיבים הקשירים היטב בגרף שזמן ריצתו לינארי בגודל הגרף. האלגוריתם מתבסס על שימוש כפול באלגוריתם חיפוש לעומק - פעם אחת על הגרף
עצמו, ופעם על הגרף ה"משוחלף"
המתקבל מהיפוך כל כיווני הקשתות.
תיאור האלגוריתם:
- ראשית מפעילים את אלגוריתם חיפוש לעומק על
, ועבור כל צומת זוכרים את זמן היציאה ממנה. - כעת מחשבים את
. הדבר ניתן לביצוע בזמן לינארי. - כעת מפעילים את אלגוריתם חיפוש לעומק שנית, הפעם על
. מתחילים את ריצת האלגוריתם מהצומת בעלת זמן היציאה הגבוה ביותר מבין אלו שחושבו בשלב 1, וכאשר האלגוריתם מסיים את הסריקה שהחלה מהצומת הזו ועליו לבחור צומת חדשה, בוחרים את הצומת בעלת זמן היציאה הגבוה ביותר מבין אלו שנשארו, וכן הלאה. - תוצאת האלגוריתם שהופעל בשלב 3 היא יער. כל אחד מהעצים שביער הוא אחד מהרכיבים הקשירים היטב שבגרף, וכולם מופיעים בו. מוציאים אותם כפלט, בהתאם למבוקש (תוצאות החיפוש לעומק בלבד אינן מספיקות, שכן הוא בוצע על הגרף המשוחלף).
הסיבה לכך שמובטח שהאלגוריתם יעבוד כהלכה היא זו: אם
הם שני רכיבים קשירים היטב בגרף כך שיש קשת מ-
אל
, אז מובטח כי זמן היציאה שחושב בשלב 1 עבור צמתי
גדול מזה שחושב עבור צמתי
(לא קיימת קשת מ-
אל
, שכן אז היו שני הרכיבים הללו מתמזגים לרכיב אחד).
על כן, בגרף המשוחלף
, לא קיימת קשת מ-
אל
(כי הקשתות הפכו את כיוונן). מכיוון שאלגוריתם החיפוש לעומק בשלב 3 מתחיל את ריצתו מהרכיב שמכיל את הצומת בעל זמן היציאה הגדול ביותר, ולכן מרכיב זה לא ניתן להגיע לרכיבים אחרים, והאלגוריתם יחשב אותו בלבד. לאחר שהאלגוריתם פעל על רכיב זה צמתיו מסומנים כך שהאלגוריתם לא ייכנס אליהם שוב, ולכן מובטח כי גם המשך פעולת האלגוריתם תחזיר את התוצאה הנכונה.

