משפט ארדש-צ'באטאל

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

בתורת הגרפים, משפט ארדש-צ'באטאל הוא משפט המספק תנאי מספיק לקיום מעגל המילטון בגרף נתון.

את המשפט הוכיחו פאול ארדש וווצלאב צ'באטאל(אנ'), במאמר שפרסמו יחדיו.

נוסח המשפט

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

המשפט אומר שאם מתקיים , אז מכיל מעגל המילטון.

הוכחת המשפט

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

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

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

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

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

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

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

לכן קיבלנו כי הקבוצה היא קבוצה בלתי תלויה באורך , סתירה.

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

סמל המכלול גמרא 2.PNG
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0