גרף קשיר – הבדלי גרסאות

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

 

ג. לכל <math>\ell</math> מתקיים <math>b_\ell = a_{\ell+1}</math>. דהיינו, סדרת הקשתות מהווה מסלול בגרף.

 

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

 

 

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

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

 

 

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

 

{{תורת הגרפים}}