אשמח מאוד לקבל סיוע בשאלה המצ"ב בגרפים

[רוצה להיות מתכנת]

אשמח מאוד לקבל סיוע בשאלה המצ"ב בגרפים

 

[אורי769]

בבקשה

א. מסעיף ב אתה יכול להסיק שב-א עליך לחפש דוגמא בה הגרף הוא 2 רגולרי או 1 רגולרי. אלה גרפים מאד פשוטים. חפש גרף דו"צ 2 רגולרי הכי פשוט שאתה יכול לחשוב עליו ותבדוק.
ב. אם r>=3 אז גם הגודל של A ושל B הוא 3 ומעלה. מאחר וב-G אין צלעות בתוך A אז ב-H כל שני קודקודים ב-A מחוברים. אז האם יתכן לפצל את A לשתי קבוצות ללא צלעות?
ג. סעיף מוזר - מה ההגדרה שניתנה לכם לגשר? האם הכוונה לצלע שהוצאתה מגדילה את מספר רכיבי הקשירות או האם משהו אחר?

 

[רוצה להיות מתכנת]

זו אכן ההגדרה שניתנה לנו לגשר. ולגבי משלים של גרף דו"צ,

האם בגרף זה לא אמורים לחבר גם בין הקודקודי שנמצאים ב-A וגם בין הקודקודים שנמצאים ב-B ?

 

[אורי769]

אוקיי... אז ככה

בסעיף א וב אין הכוונה שהצדדים של H יהיו בהכרח זהים לצדדים של G. להיפך... די ברור שב-H כל הקודקודים ב-A מחוברים ולכן זה לא יכול להיות צד.

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

 

[רוצה להיות מתכנת]

אבל קיבלתי דווקא שבגרף 1 רגולרי יש גשר

 

[רוצה להיות מתכנת]

בגרף רגולרי מדרגה 3 ומעלה נקבל בהכרח מעגל

ולכן הורדת צלע לא תפגע בקשירות. אני צודק?

 

[אורי769]

תשובות

ראשית, אתה צודק לגבי 1-רגולרי. הטענה שלי תקפה לגבי r>=2.
לגבי ההוכחה שלך - קודם כל הטענה שקיים מעגל מצריכה הוכחה. שנית, זה שיש מעגל זה לא מספיק. כי אם הצלע e אינה חלק מהמעגל אז אולי היא גשר.
אבל הטיעון שלי הרבה יותר פשוט - נניח e היא גשר. אז אחרי שהוצאת את e נשארו שני גרפים למעשה שאינם מחוברים, G1 ו-G2. נסתכל על G1. הוא דו"צ עם צדדים A1 ו-B1. מה סכום הדרגות של קודקודי A1? מה של B1?