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