קבוצת רכיבים קשירים היטב

רכיב קשיר היטב הוא קבוצת קודקודים המוכלת בגרף G כך שבין כל שני קודקודים קיים מסלול. רכיב קשיר היטב מסתיים כאשר ניתן להגיע מקודקוד אחד לקודקוד אחר בגרף G, אך לא ניתן לחזור באותה הדרך (כלומר קיימת בניהם צלע מכוונת שיוצרת מסלול חד-כיווני).

גרף הרכיבים קשירים היטב שמסומן בG-SCC מכיל בתוכו את (V-SCC, E-SCC), אם בין שני רכיבי SCC יש צלע שמגשרת בין שניהם, אזי גם בתוך E-SCC תהיה קיימת צלע בהתאם לקודקודים שב-V-SCC.

תכונות הגרף

• G-SCC הוא גרף מכוון חסר מעגלים.
• אם נבצע שחלוף בגרף, אנו נקבל את אותה קבוצת קודקודים V-SCC, וב-E-SCC אנו נקבל את אותם צלעות, כאשר כל זוג קודקדים בצלע התחלף עם האחר, גרך זה יסומן ב-G-transpose.
• אם קיימת צלע (u,v) ב-E-SCC, אזי הצלע (v,u) אינה קיימת.

מציאת קבוצת רכיבים קשירים חזק של גרף G

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

• קליקה (תורת הגרפים)

• קבוצת רכיבים קשירים היטב, באתר MathWorld (באנגלית)