גרף קשיר

קובץ:Unconnected graph.jpeg

גרף לא קשיר: אין מסלול המקשר את הקודקודים A ו-B. לגרף יש שני מרכיבי קשירות. הערה: יש לשים לב שב"הצטלבות" במרכז הגרף אין קודקוד, כך שלמעשה אין זו הצטלבות, אין קשר בין הצלעות בה.

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

פורמלית, גרף הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G=\left(V,E\right)} ייקרא קשיר אם לכל זוג צמתים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_i\,} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_j\,} ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle V\,} קיימת סדרה של קשתות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_1, e_2, \ldots, e_k} ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E\,} כך שאם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_\ell = (v_{a_\ell}, v_{b_\ell})} לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell\in\mathbb{N}} אז:

א. $a_{1}\,=i$. דהיינו, המסלול מתחיל בצומת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_i\,} .

ב. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_k\,= j} . דהיינו, המסלול מסתיים בצומת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_j\,} .

ג. לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell} מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_\ell = a_{\ell+1}} . דהיינו, סדרת הקשתות מהווה מסלול בגרף.

גרף שאינו קשיר היטב: אין מסלול מכוון מ- B ל- A. אם מבטלים את הכיווניות של הגרף, הוא הופך להיות קשיר

יש לשים לב כי ההגדרה הנ"ל משתנה קלות כאשר מדובר בגרפים לא מכוונים או בגרפים מכוונים. במקרה הראשון, קשת היא קבוצה בת שני צמתים, ואילו במקרה השני, קשת היא זוג סדור של שני צמתים.

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

רכיבי קשירות

רכיב קשירות של גרף הוא תת-גרף קשיר מקסימלי, כלומר, קבוצת קודקודים שיש מסלול בין כל שני קודקודים שלה, והכוללת עם כל קודקוד גם את השכנים שלו; יחד עם הקשתות המחברות את הקודקודים האלה. כל גרף מתפרק באופן יחיד לרכיבי קשירות.

רכיב קשיר היטב

גרף שבו מסומנים הרכיבים הקשירים היטב

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

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

אלגוריתמים רבים בתורת הגרפים מניחים שהגרף עליו הם פועלים קשיר היטב, ועל כן מפעילים אותם על כל רכיב קשיר היטב בנפרד.

גרף מכוון בו עבור כל שני קדקודים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle u,v \in V} קיים מסלול מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} או מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} נקרא קשיר למחצה.

גרף מכוון הנעשה קשיר לאחר הסרת הכיווניות נקרא קשיר חלש.

אלגוריתם למציאת רכיבים קשירים היטב

אלגוריתם Kosaraju הוא דרך פשוטה יחסית למציאת הרכיבים הקשירים היטב בגרף שזמן ריצתו ליניארי בגודל הגרף. האלגוריתם מתבסס על שימוש כפול באלגוריתם חיפוש לעומק - פעם אחת על הגרף $\ G$ עצמו, ופעם על הגרף ה"משוחלף" הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ G^T} המתקבל מהיפוך כל כיווני הקשתות.

תיאור האלגוריתם:

1. ראשית מפעילים את אלגוריתם חיפוש לעומק על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ G} , ועבור כל צומת זוכרים את זמן היציאה ממנו.
2. כעת מחשבים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ G^T} . הדבר ניתן לביצוע בזמן ליניארי.
3. כעת מפעילים את אלגוריתם חיפוש לעומק שנית, הפעם על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ G^T} . מתחילים את ריצת האלגוריתם מהצומת בעל זמן היציאה הגבוה ביותר מבין אלו שחושבו בשלב 1, וכאשר האלגוריתם מסיים את הסריקה שהחלה מהצומת הזה ועליו לבחור צומת חדש, בוחרים את הצומת בעל זמן היציאה הגבוה ביותר מבין אלו שנשארו, וכן הלאה.
4. תוצאת האלגוריתם שהופעל בשלב 3 היא יער. כל אחד מהעצים שביער הוא אחד מהרכיבים הקשירים היטב שבגרף, וכולם מופיעים בו. מוציאים אותם כפלט, בהתאם למבוקש (תוצאות החיפוש לעומק בלבד אינן מספיקות, שכן הוא בוצע על הגרף המשוחלף).

הסיבה לכך שמובטח שהאלגוריתם יעבוד כהלכה היא זו: אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ C_1,C_2} הם שני רכיבים קשירים היטב בגרף כך שיש קשת מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ C_1} אל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ C_2} , אז מובטח כי זמן היציאה שחושב בשלב 1 עבור צומתי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ C_1} גדול מזה שחושב עבור צומתי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ C_2} (לא קיימת קשת מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ C_2} אל $\ C_{1}$, שכן אז היו שני הרכיבים הללו מתמזגים לרכיב אחד).

על כן, בגרף המשוחלף הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ G^T} , לא קיימת קשת מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ C_1} אל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ C_2} (כי הקשתות הפכו את כיוונן). מכיוון שאלגוריתם החיפוש לעומק בשלב 3 מתחיל את ריצתו מהרכיב שמכיל את הצומת בעל זמן היציאה הגדול ביותר שהוא נמצא בהכרח ב- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ C_1} , ולכן מרכיב זה לא ניתן להגיע לרכיבים אחרים, והאלגוריתם יחשב אותו בלבד. לאחר שהאלגוריתם פעל על רכיב זה צמתיו מסומנים כך שהאלגוריתם לא ייכנס אליהם שוב, ולכן מובטח כי גם המשך פעולת האלגוריתם תחזיר את התוצאה הנכונה.

קשירות מרובה

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

גרף קשיר34411242Q230655