כמה דברים לגבי הוכחת משפט בתורת הגרפים

student47

New member
כמה דברים לגבי הוכחת משפט בתורת הגרפים

http://math-wiki.com/images/2/24/GT.L10.pdf

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

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

בחלק הזה, כתוב שיש שידוך מושלם מ-V1 ל-V2.
שאלה 1:
יש נקודה שאני רוצה להיות בטוח לגביה..יש לי את הגרף G, ועל גביו מגדירים שידוך מושלם - כלומר בין כל 2 קדקדים בשידוך, קיימת צלע בגרף, אבל יתכן שיש צלע בין 2 קדקדים בגרף, שאינה נמצאת בשידוך?

שאלה 2:
כתוב "לפי ההגדרות, לכל 2 צלעות בשידוך אין קדקד משותף". ההגדרות שעליהן מדובר הן ההגדרה של גרף דו"צ וההגדרה של שידוך מושלם?

שאלה 3:

לא ברור לי החלק שכתוב "נצבע את צלעות השידוך המושלם של G בצבע d, ונשמיט אותך מהגרף".
מה הכוונה לצבוע בצבע d?
ולמה צובעים אותן בכלל?

שאלה 4: למה בסוף, מכך שמקבלים גרף 0 רגולרי, מסתיימת ההוכחה? ההוכחה אמורה להסתיים כשמוכיחים ש-i(G)<=d .

תודה רבה לעונים ושנה טובה.
 

אורי769

New member
כבר שאלת את השאלה הזאת

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

student47

New member
ובכן

שאלתי משהו דומה. למעשה שאלתי על טענת עזר 1 מתוך ההוכחה שעליה אני מדבר, ועזרת לי להוכיח אותה (כי לא ממש הבנתי את ההוכחה שלהם עד הסוף).
כאמור, המשפט שעליו אני שואל הוא משפט 2 מהלינק, שאומר: G דו"צ d רגולרי => i(G)=d.

במהלך ההוכחה הם משתמשים ב-2 טענות עזר: הטענה הראשונה (שכאמור עזרת לי להוכיח אותה בפוסט קודם ששאלתי) היא:
יהא G גרף דו"צ d רגולרי שצדדיו V1,V2 אזי: zz |V1|=|V2| zz .
אין לי בעיה עם זה..את זה אני מבין.
אחר כך יש טענת עזר שנייה שגם את ההוכחה שלה אני מבין, שאומרת: לכל תת קבוצה A של V1, מתקיים: zz |N_G(A)| >= |A| zz .

מה שלא מובן לי, זה החלק בלינק http://math-wiki.com/images/2/24/GT.L10.pdf
שבו כתוב "המשך הוכחת המשפט" (כלומר המשך הוכחת משפט 2 מעמוד 1).

אכן אני רואה ששאלתי על זה לפני זמן מה...האמת שמה ששאלתי לא היה הכי מוגדר...ענית לי..לא ממש הבנתי אותך. זה מה שענית לי:

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

תראה..ארשום שוב את השאלות שלא מובנות לי. הן יותר ספציפיות ממה ששאלתי לפני שבועיים..ולגבי התשובה שלך, אם תוכל אולי בבקשה לנסות להסביר לי שוב. כשאמרת "בצביעה צלעית כל צבע הוא זיווג", התכוונת שהצלע הצבועה שבין שניי קדקדים (אחד מ-V1 ואחד מ-V2) היא זיווג בין שניי הקדקדים?
למה בכלל צריך לצבוע אותה (שאלות 3א',ב' כאן)? הרי התאמה בין 2 קדקדים, היא זיווג בין אם הצלע ביניהם צבועה ובין אם לא...והחלק עם האינדוקציה לא מובן לי.

בחלק שבו כתוב "המשך הוכחת המשפט", כתוב שיש שידוך מושלם מ-V1 ל-V2.

שאלה 1:
יש נקודה שאני רוצה להיות בטוח לגביה..יש לי את הגרף G, ועל גביו מגדירים שידוך מושלם - כלומר בין כל 2 קדקדים בשידוך, קיימת צלע בגרף, אבל יתכן שיש צלע בין 2 קדקדים בגרף, שאינה נמצאת בשידוך?

שאלה 2:
כתוב "לפי ההגדרות, לכל 2 צלעות בשידוך אין קדקד משותף". ההגדרות שעליהן מדובר הן ההגדרה של גרף דו"צ וההגדרה של שידוך מושלם?

שאלה 3:

לא ברור לי החלק שכתוב "נצבע את צלעות השידוך המושלם של G בצבע d, ונשמיט אותן מהגרף".
א'. מה הכוונה לצבוע בצבע d?
ב'.למה צריך לצבוע אותן בכלל?
ג'. למה משמיטים את הצלעות?

שאלה 4: למה בסוף, מכך שמקבלים גרף 0 רגולרי, מסתיימת ההוכחה? ההוכחה אמורה להסתיים כשמוכיחים ש-i(G)<=d .

אודה לך מאד אם תוכל לנסות לעזור!
 
למעלה