|
|
עמוד:331
הגרף x \ r \ G עץ , 7 = ( V , E ) אם , ורק אם , ion G מעגלים , והוספת קשת כלשה T e = ( a , b ) בין שני הקדקודים לא מחוברים G-2 a- \ b יוצרת מעגל , כלומר , בגרף , G' = ( V , E u ( a , b ) כאשר , { a , b } < t E T קיים מעגל ( אחד ויחיד ) המכיל את הקשת . ( a , b ) הגדרה : נתון גרף בלתי מכוון קשיר G- ( V , E ) קשת e בגרף G נקראת קשת מפרידה אם ה 0 רתה מגרף G תיצור גרף עם שני רכיבים . דוגמאות . 1 בגרף שלהלן : { b , d ) rwpr \ היא קשת מפרידה , ויתר הקשתות שבגרף זה אינן מפרידות . . 2 בגרף הבא שהנו עץ : כל קשת היא קשת מפרידה . . 3 בגרף שלהלן ;
|
|