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

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

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

גרף רכיבים קשירים היטב (מסומן 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) אינה קיימת.

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

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

 ראו גם 

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

קישורים חיצוניים


קטגוריה:תורת הגרפים