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

Flower snark

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

הראשון שלמד גרפים אלו היה Tait, שניסה להוכיח את משפט ארבעת הצבעים, וב-1880 הראה שדוגמא נגדית מוכרחה להיות סנרק מישורי. עד 1973 היו ידועות רק ארבע דוגמאות לסנרקים (הראשונה: גרף פטרסן מ-1898). מאז נבנו כמה משפחות אינסופיות, ופותחו פעולות הבונות משני סנרקים נתונים סנרק גדול יותר.

הגדרה

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

זרימה בגרף

גרף מדרגה 3 ניתן ל-3-צביעה אם ורק אם יש בו זרימה לא מתאפסת עם ערכים בחבורת הארבעה של קליין $\ \mathbb {Z} _{2}\times \mathbb {Z} _{2}$. (זרימה היא התאמה של ערכים לקשתות, באופן שסכום הקשתות בכל קודקוד הוא אפס).

סנרקים כדוגמאות נגדיות

יש כמה השערות ידועות בתורת הגרפים, שאם אינן נכונות צריכה להיות להן דוגמא נגדית שהיא סנרק:

• Tutte 1954: לכל גרף נטול גשרים יש זרימת-5 לא מתאפסת (זרימת-5 היא זרימה המקבלת את הערכים $0,\pm 1,\pm 2,\pm 3,\pm 4$).
• Szeckers 1973: כל גרף נטול גשרים אפשר לפרק למעגלים באופן שכל קשת שייכת בדיוק לשני מעגלים.
• Fullerson 1971: כל גרף נטול גשרים מדרגה 3 אפשר לפרק לאיחוד של ששה שידוכים כך שכל קשת שייכת בדיוק לשני שידוכים.

ידוע שיש סנרקים שהם 6-קשירים. משערים שאין סנרקים 7-קשירים.