זרימה לא מתאפסת – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
אין תקציר עריכה |
||
שורה 1:
'''זרימה לא מתאפסת''' ב[[גרף (תורת הגרפים)|גרף]] מכוון מעל [[חבורה אבלית]] היא השמה של אברי החבורה (פרט לאפס) לקשתות של הגרף כך שבכל קודקוד סכום הקשתות היוצאות יהיה
השאלה החשובה בהקשר של זרימה לא מתאפסת היא באיזה גרפים קיימת זרימה לא מתאפסת של חבורה נתונה. לכל [[חתך (תורת הגרפים)|חתך של גרף]] סכום הקשתות מתאפס. לכן בגרף עם גשר (קשת שאם מורידים אותה מספר רכיבי הקשירות גדל) אין זרימה לא מתאפסת מעל כל חבורה. מאידך, בכל גרף ללא גשר (שנקרא 2-קשיר) קיימת זרימה לא מתאפסת, מכיון שקיימת אוריינטציה של הקשתות שהופכת אותו ל[[גרף קשיר|קשיר היטב]]. משפט המפתח שהוכיח ויליאם טאט (Tutte) הוא כי קיום הזרימה תלוי אך ורק בגודל החבורה ולא במבנה שלה וכי אם יש זרימה מעל חבורה מסוימת אז יש זרימה מעל חבורה גדולה יותר. לכן ניתן להגדיר
לגרף יש זרימה-2 לא מתאפסת אם ורק אם הוא [[מסלול אוילר|אוילרי]]. טאט [[השערה|שיער]] ב-1954 כי כל גרף נטול גשרים יש זרימת-5 לא מתאפסת. ידוע בעקבות עבודותיהם של פרנסואה ז'גר ו[[פול סימור]] כי כל גרף נטול גשרים יש זרימת-6 לא מתאפסת.
לזרימה לא מתאפסת קשרים הדוקים עם [[צביעת קודקודים]] ו[[צביעת קשתות]] של גרפים. היא נחקרה לראשונה כגישה להוכחת [[משפט ארבעת הצבעים]]. ניתן להראות כי ל[[גרף מישורי]] ללא גשרים שמשוכן במישור יש זרימת-k לא מתאפסת אם ורק אם לגרף הדואלי (המתאים לפנים של הגרף המשוכן) יש צביעה בקודקודים עם k צבעים. בגרף ללא גשרים שלכל קודקודיו דרגה 3 ניתן לצבוע את קשתותיו ב-3 צבעים אם ורק אם יש לו זרימת-3 לא מתאפסת. ניתן לראות זאת על ידי שימוש ב[[חבורת הארבעה של קליין]] <math>\ \mathbb{Z}_2 \times \mathbb{Z}_2</math>.
לכן משפט ארבעת הצבעים שקול לטענה כי כל גרף מישורי ללא גשרים לכל קודקודיו דרגה 3 ניתן לצבוע את קשתותיו עם שלושה צבעים. בעיית ההכרעה האם גרף שדרגתו 3 ניתן לצביעה עם שלושה צבעים היא שלמה לNP ומכאן שגם שאלת קיום זרימת-3 לא מתאפסת היא NP שלמה.
==ראו גם==
[[סנרק (תורת הגרפים)]]
| |||