סנרק (תורת הגרפים)
בתורת הגרפים, סנרק הוא כינוי לגרף ללא גשרים שלכל קודקודיו דרגה 3, ושלא ניתן לצבוע את קשתותיו ב-3 צבעים (לפי משפט ויזינג כל גרף כזה הוא 4-צביע). הגרפים נקראים כך על שם היצור החמקמק מן הבלדה "ציד הסנרק" של לואיס קרול, על פי הצעתו של מרטין גרדנר.
הראשון שחקר גרפים מסוג זה היה פיטר טייט (Tait), שניסה להוכיח את משפט ארבעת הצבעים, וב-1880 הראה שדוגמה נגדית מוכרחה להיות סנרק שהוא גרף מישורי [1]. עד 1973 היו ידועות רק ארבע דוגמאות לסנרקים (הראשונה: גרף פטרסן מ-1898). מאז נבנו כמה משפחות אינסופיות, ופותחו פעולות הבונות משני סנרקים נתונים סנרק גדול יותר.
הגדרה[עריכת קוד מקור | עריכה]
גשר בגרף הוא קשת שהסרתה מהגרף מגדילה את מספר רכיבי הקשירות (הגדרה אלטרנטיבית לגשר היא קשת שלא משתתפת בשום מעגל). אם בגרף קשיר אין אף קבוצה בגודל k של קשתות כך שהסרתן מהגרף מגדילה את מספר רכיבי הקשירות, נאמר שהגרף k-קשיר. אם סנרק אינו 3-קשיר, או אם יש בו מעגל באורך 2, 3 או 4, אז אפשר ליצור ממנו בקלות סנרק קטן יותר. מסיבה זו, יש המגדירים סנרק כגרף מדרגה 3, בעל מותן 5 לפחות, שהוא 4-קשיר.
זרימה לא מתאפסת בגרף וצביעת קשתות[עריכת קוד מקור | עריכה]
גרף מדרגה 3 ניתן ל-3-צביעה אם ורק אם יש בו זרימה לא מתאפסת עם ערכים בחבורת הארבעה של קליין . (זרימה היא התאמה של ערכים (שאינם אפס) מחבורה לקשתות, באופן שסכום הקשתות בכל קודקוד הוא אפס. מכיוון שבחבורה זאת , אין משמעות לכיוון הקשתות).
סנרקים כדוגמאות נגדיות[עריכת קוד מקור | עריכה]
יש כמה השערות ידועות בתורת הגרפים, שאם אינן נכונות צריכה להיות להן דוגמה נגדית שהיא סנרק:
- ויליאם טאט (Tutte), 1954: בכל גרף נטול גשרים יש זרימת-5 לא מתאפסת
- גאורגה סקרש Szeckers, 1973: כל גרף נטול גשרים אפשר לפרק למעגלים באופן שכל קשת שייכת בדיוק לשני מעגלים.
- פאלקרסון Fulkerson 1971: כל גרף נטול גשרים מדרגה 3 אפשר לפרק לאיחוד של שישה שידוכים כך שכל קשת שייכת בדיוק לשני שידוכים.
ידוע שיש סנרקים שהם 6-קשירים. משערים שאין סנרקים 7-קשירים.
