הצגת המקור של הדף "משפט ארדש-צ'באטאל"

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

את המשפט הוכיחו [[פאול ארדש]] ו[[ווצלאב צ'באטאל]]{{אנ|Václav Chvátal}}, במאמר שפרסמו יחדיו.

== נוסח המשפט ==
יהי <math>G = \big(V,E\big)</math> גרף פשוט עם לפחות 3 קודקודים. יהי <math>\alpha(G)</math> מספר האי תלות של <math>G</math> (גודל [[קבוצה בלתי תלויה (תורת הגרפים)|הקבוצה הבלתי תלויה]] הגדולה ביותר) ויהי <math>K\left(G\right)</math> הקשירות הקודוקדית של G (המספר הקטן ביותר של קודקודים שיש להסיר מG על מנת להפוך אותו ל[[גרף קשיר|גרף לא קשיר]]).

המשפט אומר שאם מתקיים <math>\alpha\left(G\right) \le K\left(G\right)</math>, אז <math>G</math> מכיל [[מעגל המילטון]].

== הוכחת המשפט ==
נסמן <math>k = K \left( G \right)</math>, <math>n = \left| V \right|</math>. אז אם <math>k = 1</math> נקבל כי <math>\alpha \left( G \right) \le 1</math> ולכן <math>\alpha \left( G \right) = 1</math>. לכן בין כל שני קודקודים ב<math>G</math> יש צלע ולכן <math>G</math> [[קליק (תורת הגרפים)|קליקה]]. אבל אז <math>k = K\left( G \right) = n - 1</math>, סתירה.

לכן נוכל להניח כי <math>k \ge 2</math>. יהי <math>C</math> [[מעגל (תורת הגרפים)|המעגל]] בעל האורך הגדול ביותר ב<math>G</math>. נטען כי <math>C</math> מעגל המילטון. מאחר ש<math>k = K\left(G\right) \le \delta \left( G \right)</math> (כאשר <math>\delta \left(G\right)</math> [[דרגה (תורת הגרפים)|הדרגה המזערית]] ב<math>G</math>), מתקיים כי <math>C</math> מכיל לפחות <math>k + 1</math> קודקודים.

נסתכל בגרף <math>G \left( V \setminus V\left(C\right) \right)</math> (כלומר ב<math>G</math> בלי הקודקודים של <math>C</math> והצלעות שנוגעות בקודוקדים אלה). [[הוכחה בדרך השלילה|נניח בשלילה]] כי הוא אינו ריק. יהי <math>U</math> רכיב קשירות בגרף זה. אז בגרף המקורי <math>G</math>, קבוצת קודקודי <math>U</math> מחוברת ל<math>k</math> שכנים שונים ב<math>C</math> - אחרת נוכל לנתק את <math>U</math> מהמעגל <math>C</math> על ידי הסרת פחות מ<math>k</math> קודקודים, בסתירה לכך שהקשירות הקודקודית של <math>G</math> היא <math>k</math>.

נכוון את צלעות המעגל <math>C</math> לכיוון אחיד. תהי <math>a_1,a_2,\dotsc,a_k</math> סדרת <math>k</math> השכנים השונים שיש ל<math>U</math> על המעגל <math>C</math>, מסודרים לפי סדר הופעתם במעגל. לכל <math>1 \le i \le k</math> נסמן ב<math>u_i</math> את השכן של <math>a_i</math> ב<math>U</math> וב<math>b_i</math> את האיבר המופיע מיד אחרי <math>a_i</math> במעגל <math>C</math>. נשים לב כי איברי <math>b_i</math> שונים אחד מהשני, מכיוון שאיברי <math>a_i</math> שונים אחד מהשני.

יהי <math>u \in U</math> כלשהו. נטען כי הקבוצה <math>\left\{b_1,b_2,\dotsc,b_k\right\}\cup\left\{u\right\}</math> היא קבוצה בלתי תלויה. זה יגרור סתירה, כי זו קבוצה בלתי תלויה בגודל <math>k+1</math>, כאשר הנחנו שהקבוצה הבלתי תלויה הגדולה ביותר היא בגודל לכל היותר <math>k</math>.

נראה ראשית שאין צלע בין <math>b_i</math> ל<math>b_j</math> כאשר <math>i < j</math>. לו הייתה כזו, יכולנו ליצור מעגל באורך גדול יותר ב<math>G</math> בצורה הבאה: נתחיל ב<math>b_j</math>, נמשיך לאורך <math>C</math> עד שנגיע ל<math>a_i</math>, משם נמשיך ל<math>u_i</math> וממנו ל<math>u_j</math> (זה אפשרי כי <math>u_i</math> ו<math>u_j</math> באותו רכיב קשירות) ומ<math>u_j</math> נמשיך ל<math>a_j</math> משם נלך על <math>C</math> בכיוון הנגדי עד ל<math>b_i</math> ומשם לבסוף ניקח את הצלע <math>b_ib_j</math> כדי לחזור ל<math>b_j</math>.

בנוסף, נראה שאין צלע בין <math>b_i</math> ל-<math>u</math>, לו הייתה כזאת יכולנו לקבל מעגל ארוך יותר באופן הבא: נתחיל ב<math>b_i</math>, נמשיך לאורך <math>C</math> עד אשר נגיע ל<math>a_i</math> נמשיך ל<math>u_i</math> ומשם ל<math>u</math> (זה אפשרי כי <math>u,u_i</math> באותו רכיב קשירות) ולבסוף ניקח את הצלע <math>ub_i</math> כדי לחזור ל<math>b_i</math>.

לכן קיבלנו כי הקבוצה <math>\left\{b_1,b_2,\dotsc,b_k\right\}\cup\left\{u\right\}</math> היא קבוצה בלתי תלויה באורך <math>k + 1</math>, סתירה.

==קישורים חיצוניים==
*[https://web.archive.org/web/20170706082729/http://www.math-inst.hu/~p_erdos/1972-02.pdf  "A note on Hamiltonian circuits] 

[[קטגוריה:משפטים בתורת הגרפים|ארדש-צ'באטאל]]
[[קטגוריה:פאול ארדש]]