תוכנית פסגה · גרפים מכוונים ובעיית המנעול
תרגיל 1: גרפים מכוונים - הגדרות ותרגול
גרף מכוון: לכל קשת יש כיוון. מותר לעבור בה רק בכיוון החץ.
דרגת כניסה: מספר הקשתות שנכנסות לצומת. דרגת יציאה: מספר הקשתות שיוצאות ממנו.
מסלול אוילר מכוון: עובר בכל קשת בדיוק פעם אחת, בכיוון החצים. אם ההתחלה והסיום באותו צומת, זהו מעגל אוילר.
לולאה: קשת מצומת אל עצמו. היא מוסיפה 1 לדרגת הכניסה ו־1 לדרגת היציאה. שני חצים מנוגדים בין צמתים הם שתי קשתות נפרדות.
- רשמו את דרגת הכניסה ואת דרגת היציאה של כל צומת. רק לאחר מכן הפעילו את הצגת הדרגות ובדקו.
- האם הרצף 1 → 2 → 2 → 3 → 1 חוקי? האם הוא מעגל אוילר של הגרף? נמקו.
- האם אפשר לעבור מצומת 1 ישירות לצומת 3? האם מעבר מצומת 2 לעצמו נחשב שימוש בקשת?
- מצאו רצף שמשתמש בכל הקשתות בדיוק פעם אחת. מותר לבקר בצומת שוב.