שאלה בתורת הגרפים.

[gil levi]

שאלה בתורת הגרפים.

יהי G=(V,E)zzz גרף פשוט עם 101 קודקודים ודרגה מינימלית 51, ויהי v קודקוד בG. הוכח שG מכיל מעגל פשוט באורך 27 בדיוק שמכיל את v. מהנתון שהדרגה המינימלית היא 51 נובע שG המילטוני, כלומר מכיל מעגל המילטון, אבל אין לי מושג איך להתקדם מעבר לכך. תודה מראש.

 

[vinney]

המם...

נניח שיש לנו גרף דו צצדי של 100 קודקודים עם 50 קודקודים בכל צד, כשמכל קודקוד מצד מסוים, יש קשת לכל קודקוד בצד אחר. בנוסף, יש קודקוד נוסף, שיש קשת ממנו לכל אחד משאר הקודקודים. גרף כזה עונה על התיאור (101 קודקודים עם דרגה מינימלית 51). בגרף כזה, לכל צומת יש מעגל פשוט הכולל אותו, באורך אי זוגי בכל גדול מ3 וקטן מ101, כולל 27. השאלה היא האם יש גרף אחר שיכול לענות לתנאים (של 101 צמתים עם דרגה של 51 לפחות), אבל לא ניתן על ידי הסרות קשתות ליצור ממנו את הגרף שתיארתי בהתחלה (זאת אומרת שיהיו שם קשתות שבגרף דו צדדי שתיארתי קודם לא יהיו). לדעתי לא. אם תוכיח את זה - ענית על השאלה. אלא אם כן אני שוב מסטול מדי

 

[vinney]

הפוך

שלא יהיו בגרף האחר קשתות שיש בגרף הדו צדדי. וזה קטן שווה מ101, ה101 זה המעגל ההמילטוני שכמו שאמרת - ישנו.

 

[gil levi]

תודה רבה, הבעיה נפתרה.