השערת הכיסוי הכפול במעגלים

קומבינטוריקה היא תורת הקבוצות הסופיות. היא דנה במבנים שכל מה שיש בהם הוא איברים ויחסים ביניהם, בדרך כלל מספר סופי של איברים, ואז גם היחסים סופיים, כמובן.

תורת הגרפים היא חלק מן הקומבינטוריקה, חלק שנשמע כאילו הוא אמור להיות טריוויאלי לגמרי: תורת הקבוצות מגודל \({2}\). גרף הוא קבוצה \({V}\) של נקודות, או בשם הרשמי יותר “קדקודים” (\({vertices}\))- מכאן הסימון \({V}\), בצירוף אוסף זוגות מתוכן. לזוגות קוראים “צלעות”(\({edges}\)).

מה כבר אפשר לומר על אובייקט כל כך פשוט? הרבה מאוד דברים. הנה למשל משפט מפורסם, שהתגלה לראשונה על ידי מנטל, והתגלה מחדש והוכלל על ידי המתמטיקאי פול טורן שסיפורו הופיע באחד הגליונות הקודמים. אגב – את המשפט הזה גילה טורן בזמן שהיה כלוא במחנה עבודה גרמני במלחמת העולם השנייה .

משפט 1

בגרף על \({n}\) קדקודים עם יותר מ-\({\frac{n^2}{4}}\) צלעות יש משולש.

האם אתם יכולים להראות שהמספר \({\frac{n^2}{4}}\) הוא אכן הטוב ביותר? או אולי אפילו להוכיח את המשפט?

על כך שהפשטות לכאורה שת תורת הגרפי מטעה מלמדת גם העובדה שיש בה הרבה מאוד השערות, שנשמעות פשוטות מאוד, ובכל זאת עומדות בפני מאמציהם של המתמטיקאים לאורך שנים רבות. כאן נספר על אחת מהן: השערת הכיסוי הכפול במעגלים. “מעגל” הוא מה שהוא נשמע – אוסף צלעות שמחבר סדרת קדקודים כל האחד לעוקבו, והאחרון לראשון.

אם בגרף כל צלע משתתפת במעגל, אז יש אוסף מעגלים שמכסה כל צלע בגרף בדיוק פעמיים.

כדי להבין את ההשערה, רשמו תחילה גרף שבו יש צלע שאינה משתתפת במעגל. אחר כך נסו את ההשערה בדוגמאות הבאות:

א. מעגל אחד.

ב. גרף המורכב מ-\({4}\) קדקודים, שכולם מחוברים זה לזה.

ג. גרף המורכב מ-\({5}\) קדקודים, שכולם מחוברים זה לזה.

ד. גרף המורכב מ-\({n}\) קדקודים, שכולם מחוברים זה לזה.

ההשערה הזאת פורסמה לראשונה על ידי סקרש )\({George~~Szekeres}\), חבר של פואל ארדש שהיגר מהונגריה לאוסטרליה( ב-\({1973}\), והתגלתה מחדש באופן בלתי תלוי על ידי פאול סימור ב-\({1980}\). נעשתה בה מעט מאוד התקדמות מאז – אתם מוזמנים לנסות את כוחכם!

הנה היא ההשערה בויקיפדיה: \({http://en.wikipedia.org/wiki/Cycle_double_cover}\)