פרק זה אינו אחרוך במיוחד וקל
להבנה. רק"ח - רכיבי קשירות חזקה, הוא חילוק העץ לקבוצות
של קודקודים, חילוק עליו נדבר בהמשך. בעמוד זה נסביר מהם
רק"חים, ונסביר גם מהו גרף הופכי. בעמוד הבא נציג את
האלכוריתם המחלק גרף לרכיגי קשירות ובסוף הפרק יבואו כמובן
שאלות לתלמיד.
למה זה טוב
פירוק גרף לרכיבים הקשורים
היטב (הגדרה מדוייקת בהמשך) הוא פעולה ראשונה שאלגוריתמים
רבים מבצעים, והא מאפשר לחלק בעיות רבות לתתי בעיות, על
מנת לפותרן ביעילות רבה יותר.
מעבר לזה, שהו שימוש קלאסי
לסריקת עומק של גרף, ולמעשה פרק זה מהווה סיכום ויישום של
הפרק - סריקה בגרף. מומלץ להעזר בפרק זה, כדי לסגור את החומר
הקודם לפני שעוברים לאלגוריתמים מתקדמים בתורת הגרפים.
מהו רק"ח
רכיב קשירות היטב (או רכיב
קשירות חזקה) הוא קבוצת קודקודים מקסימלית בתוך הגרף, בה
יש מסלול מכל קודקוד לכל קודקוד. הדוגמא הבאה מראה זאת בצורה
ברורה ביותר. לחץ על 'הצג' כדי לראות את רכיבי הקשירות:
רכיבי הקשירות, עם הקשתות המחברות
בינהם, נקראים יחד - גרף רכיבי הקשירות או גרף העל.
מהו הגרף ההופכי
האלגוריתם בעמוד הבא, משתמש
בגרף ההופכי של גרף נתון. גרף הופכי לגרף מכוון כלשהו, הוא
גרף המכיל את אותם הקודקודים, אך כל קשתותיו פונים לכיוון
ההפוך. כלומר הקשת (i,j) בגרף המקורי תהיה הקשת (j,i) בגרף
ההופכי. לחץ על הצג כדי לראות את הגרף ההופכי:
האם שמת לב
רכיבי הקשירות של גרף הופכי
הם בדיוק אותם רכיבי הקשירות של הגרף המקורי. גרף העל של
הגרף ההופכי הוא הגרף ההופכי של גרף העל המקורי. לא מבין?
לא מאמין? לחץ הצג כדי להשתכנע:
