גרפים, הוכחת המשפט G קשיר או המשלים שלו קשיר

[iso532]

גרפים, הוכחת המשפט G קשיר או המשלים שלו קשיר

שלום! אשמח לסיוע בהוכחת המשפט הנ"ל
אני יודע שהמשפט נכון וגם ניסיתי להוכיח אותו אך אני לא יודע אם באופן טוב מספיק.
חשבתי על משהו כזה..
נניח שהגרף היה לא קשיר, כלומר היה בו לפחות שני רכיבי קשירות נניח רכיב א' וב'. כעת נבחן את המשלים. בגרף המשלים תהיה קשת מכל קודקוד ברכיב א' לכל קודקוד ברכיב ב'. כמו כן בהכרח יש מסלול בין כל הקודקודים שהיו ברכיב א' דרך קודקוד מרכיב ב'. הסבר: שהרי מכל קודקוד ברכיב א' יש קשת לקודקוד בב' ומקודוקד זה נוכל להגיע לכל קודקוד בא'.
באותו אופן גם קודקודי רכיב ב' נשארו קשירים כי אפשר להגיע מכל קודקוד ברכיב ב' לכל קודקוד ברכיב דרך קודקוד מרכיב א'.
מ.ש.ל.
1. האם הוכחה זו מספקת?
2. אני חש שזה לא מספיק "מתמטי" יש דרך יותר טובה להוכיח את זה?

תודה!!

 

[אורי769]

זה בסדר גמור

נקודה קטנה שיכולה לעשות את הניסוח לפשוט יותר וגם יותר מדויק היא לא להניח קיומם של רכיב א וב ולהוכיח לגביהם, אלא לומר כך:
נניח x,y קודקודים. יש שתי אפשרויות
1. הם ברכיבי קשירות שונים של G. לכן הם מחוברים במשלים.
2. הם באותו רכיב קשירות של G. לכן קיים קודקוד z ברכיב אחר ואז x--z--y הוא מסלול בין x ל-y במשלים.
זה למעשה מה שעשית רק בניסוח שבו יותר קל להשתכנע שכסינו את כל האפשרויות.

 

[iso532]

תודה!