זרימה לא מתאפסת – הבדלי גרסאות

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

 

 

לזרימה לא מתאפסת קשרים הדוקים עם [[צביעת קודקודים]] ו[[צביעת קשתות]] של גרפים. היא נחקרה לראשונה כגישה להוכחת [[משפט ארבעת הצבעים]].