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

[עריסטו]

נתון גרף מישורי ורוצים לשרטט אותו במישור בלי חיתוכים בין הקשתות. האם ייתכן שנעשה טעות בנסיון לשרטט? כלומר האם ייתכן שנשרטט חלק מהקשתות (בלי חיתוכים) אבל נעשה זאת באופן כזה שלא נוכל להשלים את הגרף ללא חיתוכים? הקשתות לא חייבות להיות ישרות.
דוגמה: הגרף K5 ללא אחת הקשתות הוא מישורי. האם ניתן לשרטט במישור חמישה קדקודים 1 2 3 4 5 ולשרטט שמונה מהקשתות 12 13 14 15 23 24 25 34 35 ללא חיתוכים, באופן כזה שלא נוכל להוסיף את הקשת התשיעית? אם זה בלתי אפשרי, האם יש גרף מישורי אחר שבו ניתן להיתקע בלי אפשרות להשלים את השרטוט?
עריכה: תשכחו את השאלה הזאת... ברור שייתכן. למשל, אם הרשתות של הגרף הן 15 23 24 34, זהו גרף מישורי. אבל אם משרטטים את הקשתות 23 24 34 כך שהן יפרידו בין הקדקוד 1 לקדקוד 5, אי אפשר להשלים את הגרף ללא חיתוך בין הקשתות.

 

[Lucifer LightBringer]

תורת הגרפים זה נושא מאוד קשה.
אני זוכר דיון של Fingertip מהאו"פ שהוא אמר שהתחום הזה מרגיש לו יותר מידי נפנופי ידיים.
אם אתה רוצה לנסות לענות על שאלות קשות תנסה מהמבחן שהיה לי. חבל שלא ניגשתי למועד ב', בתקופת התואר הראשון במועד ב' בדרך כלל הייתי משפר.
אולי הייתי מסיים עם ממוצע 89? לא נראה לי שזה היה משנה למען האמת.

כמעט כולם סיימו עם דוקטורט...מאז.
הקטע עם דוקטורט שצריך להתמחות בתחום אחד ואני מעדיף להיות Jack of all trades...