זרימה לא מתאפסת – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ בשלני העביר את הדף זרימה (תורת הגרפים) ל־זרימה לא מתאפסת: השם הקודם מוטעה - יצור קצת אחר |
אין תקציר עריכה |
||
שורה 1:
'''זרימה לא מתאפסת''' ב[[גרף (תורת הגרפים)|גרף]] מכוון מעל [[חבורה אבלית]] היא השמה של אברי החבורה (פרט לאפס) לקשתות של הגרף כך שבכל קודקוד סכום הקשתות היוצאות יהיה שוות לסכום הקשתות הנכנסות. דרישה זאת נקראת לעיתים "חוק קירכהוף". בגרף לא מכוון נוסף להשמה לקשתות צריך להוסיף אוריינטציה לקשתות. אם קימת זרימה לא מתאפסת של חבורה מסוימת עם אורינטציה אחת של הגרף אז קימת זרימה לא מתאפסת עם אורינטציה אחת, מכיון ש[[חבורה]] סגורה למשלים. לכן ניתן לדבר על קיום זרימה לא מתאפסת ללא ציון האורינטציה.
השאלה החשובה בהקשר של זרימה לא מתאפסת היא באיזה גרפים קימת זרימה לא מתאפסת של חבורה נתונה. לכל [[חתך (תורת הגרפים)|חתך של גרף]] סכום הקשתות מתאפס. לכן בגרף עם גשר (קשת שאם מורידים אותה מספר רכיבי הקשירות גדל) אין זרימה לא מתאפסת מעל כל חבורה. מאידך, בכל גרף ללא גשר (שנקרא 2-קשיר) קימת זרימה לא מתאפסת, מכיון שקימת אורינטציה של הקשתות שהופכת אותו ל[[גרף קשיר|קשיר היטב]]. משפט המפתח
לגרף יש זרימה-2 לא מתאפסת אם ורק אם הוא [[מסלול אוילר|אוילרי]].
לזרימה לא מתאפסת קשרים הדוקים עם [[צביעת קודקודים]] ו[[צביעת קשתות]] של גרפים. היא נחקרה לראשונה כגישה להוכחת [[משפט ארבעת הצבעים]].
| |||