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

דוגמה לקבוצת רכיבים קשירים חזק.

קבוצת רכיבים קשירים היטב (באנגלית: Strongly Connected Component, SCC) היא חלוקה של גרף מכוון וקשיר לרכיבים קשירים היטב, כאשר כל רכיב קשיר היטב מחובר למשנהו באמצעות צלע מכוונת (חד-כיוונית), מה שמביא לידי קבלת גרף מכוון וקשיר העשוי מקבוצת רכיבים קשירים היטב.

הגדרה

רכיב קשיר היטב הוא קבוצת קודקודים המוכלת בגרף 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.