משפט טורן

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
גרף טורן במקרה n=13, t=4

בתורת הגרפים, משפט טורן הוא משפט הקובע, בהינתן מספר קבוע של צמתים, את הגרף עם מספר הקשתות המקסימלי שאינו מכיל תת-גרף שלם (קליקה) מגודל נתון. את המשפט הוכיח המתמטיקאי ההונגרי פאול טורן (Paul Turán) בשנת 1941.

ביתר פירוט, המשפט קובע כי הגרף עם n צמתים שאינו מכיל קליקה \ K_{t+1} ומספר קשתותיו הוא מקסימלי הוא גרף שמחולק ל-t קבוצות זרות של צמתים מאותו הגודל (עד כמה שהדבר ניתן), ושלכל צומת יש קשת לכל צומת בקבוצה אחרת ולאף צומת בקבוצה שלה. גרף כזה נקרא גרף טורן.

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

רקע והגדרה פורמלית[עריכת קוד מקור | עריכה]

גרף טורן \ T(n,t) הוא גרף עם n צמתים שמחולק ל-t קבוצות זרות של צמתים. מתוכן יש \ n \text{ mod } t קבוצות של \ \lceil \tfrac nt\rceil צמתים ובשאר \ t-(n\text{ mod }t) הקבוצות יש \ \lfloor \tfrac nt\rfloor צמתים (לפשר הסימונים ראו חשבון מודולרי ופונקציית הערך השלם). כלומר הקבוצות שוות בגודלן ככל הניתן (ההפרשים במספר הצמתים ביניהן הוא לכל היותר 1). במקרה בו t מחלק את n מתקבל המקרה הפשוט ביותר - בכל t הקבוצות יש \ \tfrac nt צמתים בדיוק. בגרף טורן כל שני צמתים מקבוצות שונות מחוברים בקשת, וכל שני צמתים מאותה קבוצה אינם מחוברים בקשת.

משפט טורן קובע כי מבין כל הגרפים עם n צמתים שאינם מכילים קליקה \ K_{t+1}, ל-\ T(n,t) יש את מספר הקשתות הגדול ביותר.

קל לחשב את מספר הקשתות ב-\ T(n,t). למען הפשטות נעסוק במקרה בו t מחלק את n. בין כל שתי קבוצות יש \ \tfrac nt\cdot \tfrac nt = \tfrac{n^2}{t^2} קשתות (לפי עקרון הכפל, כי לכל אחד מבין \ \tfrac nt הצמתים בקבוצה הראשונה יש קשת לכל אחד מבין \ \tfrac nt הצמתים בקבוצה השנייה). ובסך הכל ישנם \ \tbinom t2 = \tfrac{t(t-1)}2 זוגות של קבוצות (ראו מקדם בינומי ומספר משולשי). ואין אף קשת נוספת בגרף. לכן מספר הקשתות הכולל ב-\ T(n,t) כאשר t מחלק את n הוא:

\ \frac{t(t-1)}2\cdot \frac{n^2}{t^2} = \left(1-\frac1t\right)\frac{n^2}2

לכן משפט טורן קובע שזהו חסם עליון על מספר הקשתות המקסימלי בגרף עם n צמתים שאינו מכיל קליקה \ K_{t+1} (תקף גם כאשר t אינו מחלק את n). לשם השוואה, בהיעד הגבלה על גודל הקליקה המותרת, הגרף המקסימלי הוא הגרף השלם \ K_n שלו \ \tbinom n2 = \tfrac{n(n-1)}2 קשתות.

הוכחות[עריכת קוד מקור | עריכה]

ידועות הוכחות רבות למשפט טורן. הספר Proofs from THE BOOK, שמאגד הוכחות יפות, מביא חמש הוכחות שונות למשפט.

הוכחה באינדוקציה[עריכת קוד מקור | עריכה]

ההוכחה המקורית של טורן הראתה שמספר הקשתות של גרף טורן אכן חוסם את מספר הקשתות האפשרי תחת התנאי הנתון. ההוכחה נעשית באינדוקציה על n לכל t קבוע.

נסמן ב-\ G_n את גרף עם n צמתים ועם מספר הקשתות מקסימלי שמקיים את התנאי (קיים כזה כי מספר הקשתות חסום על ידי המקרה השלם). אם \ n\le t אז \ G_n = K_n (כי בכל מקרה אי אפשר להכיל קליקה עם יותר צמתים מבגרף עצמו). ואז מספר הקשתות מקיים:

\ \frac{n(n-1)}2 = \left(1-\frac1n\right)\frac{n^2}2 \le \left(1-\frac1t\right)\frac{n^2}2

ולכן המשפט נכון לכל n כזה (כולל n=1 שהוא בסיס האינדוקציה). עתה נניח כי \ n>t. \ G_n מכיל את \ K_t, אחרת ניתן להוסיף לו קשת בלי לקבל את \ K_{t+1} בסתירה למקסימליות שלו. נחלק את הצמתים של \ G_n לשתי קבוצות זרות, \ G_1 שמכילה את צמתי הקליק \ K_t ו-\ G_2 שמכילה את שאר הצמתים בגרף. ב-\ G_1 יש \ \tfrac{t(t-1)}2 קשתות. ב-\ G_2 יש \ n-t צמתים, ולכן לפי הנחת האינדוקציה יש בה לכל היותר \ (1-\tfrac1t)\tfrac{(n-t)^2}2 קשתות. בין כל צומת ב-\ G_2 לבין קבוצת הצמתים ב-\ G_1 יש לכל היותר \ t-1 קשתות. אחרת הם יוצרים יחדיו קליקה \ K_{t+1} בניגוד לתנאי. כלומר בין \ G_1 ל-\ G_2 יש לכל היותר \ (n-t)(t-1) קשתות. נחבר הכל יחדיו כדי לקבל חסם על מספר הקשתות ב-\ G_n:

\ \frac{t(t-1)}2 + \left(1-\frac1t\right)\frac{(n-t)^2}2 + (n-t)(t-1) = \left(1-\frac1t\right)\frac{n^2}2

כנדרש.

הוכחה ישירה[עריכת קוד מקור | עריכה]

להלן הוכחה ישירה כי גרף \ G עם n צמתים ועם מספר הקשתות מקסימלי שמקיים את התנאי הוא בהכרח גרף טורן.

נוכיח כי היחס "אין קשת בין \ u ל-\ v" הוא יחס שקילות בין הצמתים בגרף:

  • רפלקסיביות: לעולם אין קשת בין צומת לעצמה.
  • סימטריות: אם אין קשת בין \ u ל-\ v אז אין קשת בין \ v ל-\ u.
  • טרנזיטיביות: נניח בשלילה כי היחס אינו טרנזיטיבי. כלומר קיימים צמתים \ u, v, w כך שאין קשתות \ (u,v) ו-\ (v,w), אבל ישנה קשת \ (u,w). נסמן ב-\ d(v) את הדרגה של \ v. נפצל לשלושה מקרים:
    • \ d(u)>d(v) - נמחק את הצומת \ v מהגרף ונחליפה בצומת \ u' שהיא העתק של הצומת \ u (מחוברת לאותם צמתים). מצד אחד לא נוצרה קליקה גדולה יותר, כי לכל קליקה ש-\ u' חבר בה, יש קליקה מגודל זהה ש-\ u חבר בה, ומצד שני הגדלנו את מספר הקשתות בסתירה למקסימליות של \ G.
    • \ d(w)>d(v) - אנלוגי למקרה הקודם, כאשר \ u' מוחלף ב-\ w'.
    • \ d(v)\ge d(u),d(w) - נמחק את \ u ו-\ w שיחדיו מחוברים אליהם \ d(u)+d(w)-1 קשתות (פחות אחד, כי הקשת ביניהם נספרת פעמיים). ונחליפם בשני עותקים של \ v. כמו קודם, לא נוצרות קליקות גדולות יותר. בסך הכל מספר הקשתות גדל ב-\ 2d(v) - (d(u)+d(w)-1)\ge 1 בסתירה למקסימליות של \ G.

הוכחנו כי "אין קשת בין \ u ל-\ v" הוא יחס שקילות בין צמתי \ G. לכן צמתי \ G מתחלקים למחלקות שקילות, כך שבין כל שני צמתים יש קשת אם ורק אם הם ממחלקות שקילות שונות. מספר מחלקות השקילות קטן מ-\ t+1, אחרת נוכל לבחור נציג אחד מכל מחלקת שקילות ונקבל קליקה \ K_{t+1} בניגוד לתנאי. מצד שני, \ G בהכרח מכיל קליקה \ K_t, אחרת ניתן להוסיף לו קשת בלי לקבל את \ K_{t+1} בסתירה למקסימליות שלו. צמתים שונים בקליקה \ K_t חייבים להיות ממחלקות שקילות שונות, כי יש ביניהם קשת, ומכאן שיש בדיוק \ t מחלקות שונות.

עד כה קיבלנו שצמתי \ G מחולקים ל-\ t מחלקות זרות, כך שכל צומת מקושרת לכל צומת מקבוצה אחרת ולאף צומת מהקבוצה שלה. כדי להוכיח כי \ G גרף טורן נותר רק להראות שכל המחלקות כמעט באותו הגודל (ההפרש ביניהן הוא לכל היותר 1). נשים לב כי לכל מחלקה \ A ולכל צומת \ v\in A מתקיים \ d(v) = n-|A| (v מקושר לכל הצמתים שלא ב-A). נניח בשלילה כי ישנה מחלקה \ A_1 שיש בה לפחות שני צמתים יותר מבמחלקה אחרת \ A_2. נמחק צומת מ-\ v מ-\ A_1 ונוסיף צומת ב-\ v' ל-\ A_2. מספר הקשתות שיתווספו הוא: \ d(v')-d(v) = (n-(|A_2|+1)) - (n-|A_1|) = |A_1|-|A_2|-1\ge 1 , בסתירה למקסימליות של \ G.

מכאן ש-\ G הוא בהכרח גרף טורן.

המקרה t=2[עריכת קוד מקור | עריכה]

משפט טורן למקרה הפרטי t=2 ידוע עוד משנת 1907 ושמו משפט מאנטל. המשפט קובע שהגרף המקסימלי מגודל n שאינו מכיל משולשים (קליקה \ K_3) הוא גרף דו צדדי שבכל צד מופיעים חצי מהצמתים (אם n אי-זוגי, בצד אחד יש אחד יותר). וכל צומת מקושרת לכל הצמתים מהצד השני (זהו \ T(n,2)). מספר הקשתות במקרה כזה יהיה \lfloor \tfrac{n^2}4 \rfloor, בערך חצי ממספר הקשתות האפשריות ללא הגבלת משולשים.

הכללה של משפט מאנטל אומרת שכל גרף עם n צמתים ולפחות \ \tfrac{n^2}4 קשתות הוא או גרף טורן \ T(n,2), או שהוא מכיל מעגל מכל אורך שהוא עד n (ולא רק משולש).

קישורים חיצוניים[עריכת קוד מקור | עריכה]