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

 

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

==ראו גם==

* [[סנרק (תורת הגרפים)]]