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

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

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