5 . 3 . 1 גרף קשיר לפני שנתאר באופן פורמלי את הבעיה עלינו להגדיר מהו גרף קשיר : רכיב קשיר - ( connected complete ) קבוצה מקסימלית של קדקודים בגרף לא מכוון שבה יש מ 0 לול פשוט בין כל שני קדקודים בגרף . קדקוד בודד ללא שכנים ייקרא גם כן רכיב קשיר . דוגמה 5 . 5 להלן גרף י בגרף ישנו רכיב קשיר אחד { a , b , c , d , e ] מאחר שמכל קדקוד קיים מסלול לכל קדקוד אחר . לעומת זאת , בדוגמה 5 . 6 מוצג גרף שבו ישנם שלושה רכיבים קשירים . דוגמה 5 . 6 להלן גרף ו נמנה את הרכיבים הקשירים בגרף : רכיב קשיר אחד הוא הקבוצה , { A , B , C , D ) מאחר שבקבוצה זו יש מסלול פשוט בין כל שני קדקודים בגרף . לקבוצה הזאת לא ניתן לצרף אף אחד מן הקדקודים E , F , G מאחר שלדוגמה אין מסלול מקדקוד A £ -ל או irtf או ל-ס .
אל הספר