נושא: גרפים

נשלח בתאריך: 28 September 2007 בשעה 09:24 | IP רשוּם

נתון גרף G פשוט, קודקודיו הם כל תתי הקבוצות בגודל 2 מעל 1-10 והקודקודים סמוכים אם יש איבר בקבוצה הראשונה אל מול איבר בקבוצה השניה שמשלימים ל-10.

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

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

תודה