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

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

 

 

לזרימה לא מתאפסת קשרים הדוקים עם [[צביעת קודקודים]] ו[[צביעת קשתות]] של גרפים. היא נחקרה לראשונה כגישה להוכחת [[משפט ארבעת הצבעים]]. ניתן להראות כי ל[[גרף מישורי]] ללא גשרים שמשוכן במישור יש זרימת-k לא מתאפסת אם ורק אם לגרף הדואלי (המתאים לפנים של הגרף המשוכן) יש צביעה בקודקודים עם k צבעים. בגרף ללא גשרים שלכל קודקודיו דרגה 3 ניתן לצבוע את קשתותיו ב-3 צבעים אם ורק אם יש לו זרימת-3 לא מתאפסת. ניתן לראות זאת על ידי שימוש ב[[חבורת הארבעה של קליין]] <math>\ \mathbb{Z}_2 \times \mathbb{Z}_2</math>.