משפט טורן

גרף טורן במקרה n=13, t=4

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

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

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

רקע והגדרה פורמלית

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

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

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

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

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

הוכחות

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

הוכחה באינדוקציה

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

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

$\ {\frac {n(n-1)}{2}}=\left(1-{\frac {1}{n}}\right){\frac {n^{2}}{2}}\leq \left(1-{\frac {1}{t}}\right){\frac {n^{2}}{2}}$

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

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

כנדרש.

הוכחה ישירה

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

נוכיח כי היחס "אין קשת בין $\ 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)$ - אנלוגי למקרה הקודם.
  • $\ d(v)\geq d(u),d(w)$ - נמחק את $\ u$ ו-$\ w$ שיחדיו מחוברים אליהם $\ d(u)+d(w)-1$ קשתות (פחות אחד, כי הקשת ביניהם נספרת פעמיים). ונחליפם בשני עותקים של $\ v$. כמו קודם, לא נוצרות קליקות גדולות יותר. בסך הכל מספר הקשתות גדל ב-$\ 2d(v)-(d(u)+d(w)-1)\geq 1$ בסתירה למקסימליות של $\ G$.

הוכחנו כי "אין קשת בין $\ u$ ל-$\ v$" הוא יחס שקילות בין צמתי $\ G$. לכן צמתי $\ G$ מתחלקים למחלקות שקילות, כך שבין כל שני צמתים יש קשת אם ורק אם הם ממחלקות שקילות שונות. מספר מחלקות השקילות קטן מ-$\ t+1$, אחרת נוכל לבחור נציג אחד מכל מחלקת שקילות ונקבל קליקה $\ K_{t+1}$ בניגוד לתנאי. מצד שני, $\ G$ בהכרח מכיל קליקה $\ K_{t}$, אחרת ניתן להוסיף לו קשת בלי לקבל את $\ K_{t+1}$ וזאת בסתירה למספר הקשתות המקסימלי של $\ G$. צמתים שונים בקליקה $\ 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}$. מספר הקשתות שיתווספו ל- $\ G$ הוא: $\ d(v')-d(v)=(n-(|A_{2}|+1))-(n-|A_{1}|)=|A_{1}|-|A_{2}|-1\geq 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 (ולא רק משולש).

קישורים חיצוניים

• גדי אלכסנדרוביץ', משפט טורן והולדת תורת הגרפים האקסטרמלית, באתר "לא מדויק", 2 בספטמבר 2011