סיכום שיעור 3 - גרפים מכוונים ובעיית המנעול

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

1. ההגדרות החדשות

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

חצים מנוגדים בין אותם צמתים הם קשתות שונות. עצם קיומו של חץ בכיוון אחד אינו מאפשר לעבור בכיוון ההפוך.

הרצף 1 → 2 → 2 → 3 → 1 חוקי וסגור, אבל אינו מעגל אוילר: הקשת 2 → 1 חסרה. אין קשת 1 → 3. מסלול אוילר אפשרי: 2 → 1 → 2 → 2 → 3 → 1.

2. מתי קיים מסלול או מעגל מכוון?

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

בגרף מכוון לא מספיק לספור כמה קשתות מחוברות לצומת: צריך להבחין בין הנכנסות ליוצאות. בדרך כלל אי אפשר להפוך מסלול חוקי וללכת בו בכיוון ההפוך.

בגרפים ג ו־ד מספר הקשתות בכל צומת זהה. היפוך חץ אחד שינה את מאזן הכניסות והיציאות, ולכן שינה את האפשרות למצוא מסלול.

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

3. למה התנאים גם מספיקים?

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

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

בגרף ד, למשל, משלבים את 1 → 2 → 3 → 1 עם 3 → 4 → 5 → 3 בצומת 3, ומקבלים 1 → 2 → 3 → 4 → 5 → 3 → 1.

למסלול פתוח מוסיפים זמנית קשת מהסיום להתחלה. כך מתקבל איזון. בונים מעגל, מסירים את הקשת הזמנית וחותכים את המעגל במקום שלה.

4. ספירת הקודים וחסם תחתון (תרגיל 3)

כמה קודים יש למנעול?

בשמונה כפתורים יש 8 × 8 = 64 זוגות ספרות אפשריים: שמונה אפשרויות לספרה הראשונה, ולכל אחת שמונה אפשרויות לשנייה. אבל רק הקודים שברשימה תקפים.

בשבע שורות יש ארבעה קודים, ובשורה שמתחילה ב־7 יש חמישה. לכן יש 7 × 4 + 5 = 33 קודים תקפים. 14 ו־41 הם קודים שונים; 11 תקף, ו־12 אינו תקף.

לאחר שמזהים את המבנה אפשר לספור גם כך: בקבוצה {1, 4, 6, 7} כל זוג ספרות תקף, וכך גם בקבוצה {2, 3, 5, 8}. נוסף על אלה יש רק את 72. לכן 4² + 4² + 1 = 33.

חסם תחתון אינו עדיין פתרון

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

ברצף 1414 נבדקים 14, 41, 14 - שלוש בדיקות, אך רק שני קודים תקפים שונים. ברצף 123 נבדקים 12 שאינו תקף ו־23 שתקף: שתי בדיקות אך רק קוד תקף אחד.

ברצף של L לחיצות יש L − 1 זוגות סמוכים, ולכן אפשר לבדוק לכל היותר L − 1 קודים תקפים שונים.

5. מהלחיצות לגרף - ומהגרף להוכחה (תרגילים 4-5)

הצמתים הם הספרות 1-8. כל קוד תקף הוא קשת מכוונת מהספרה הראשונה לשנייה. 11 הוא לולאה; 14 ו־41 הם שני חצים שונים. זוג ספרות שאינו קוד תקף אינו קשת בגרף.

בצומת 7 יש חמש יציאות וארבע כניסות, ולכן מסלול אוילר חייב להתחיל בו. בצומת 2 יש חמש כניסות וארבע יציאות, ולכן הוא חייב להסתיים בו. בכל שאר הצמתים יש ארבע כניסות וארבע יציאות. הגרף מחובר כשמתעלמים מהכיוונים, ולכן יש מסלול אוילר פתוח ואין מעגל אוילר.

המעבר שצריך לדחות: הקשת 7 → 2 היא היחידה שעוברת בין שתי הקבוצות. במסלול שמשיג את החסם צריך לנצל תחילה את כל 16 הקשתות בתוך {1, 4, 6, 7}, במעגל שמתחיל ומסתיים ב־7. אז עוברים ל־2 ומשלימים את 16 הקשתות בתוך {2, 3, 5, 8}, במעגל שמתחיל ומסתיים ב־2.

אם משתמשים ב־72 מוקדם מדי, אין קשת תקפה שמחזירה לקבוצה הראשונה. אפשר עדיין לחזור בהקלדה של קוד שאינו ברשימה, אבל הדבר מוסיף לחיצה שאינה מכסה קוד תקף חדש, ולכן כבר אי אפשר להגיע ל־34 לחיצות.

הלחיצה הראשונה קובעת את צומת ההתחלה. כל מעבר בקשת מוסיף לחיצה אחת על ספרת היעד. לכן 33 קשתות נותנות 34 לחיצות.

הוכחת המינימום: אי אפשר בפחות מ־34, ובנינו רצף של 34 שמצליח. לכן זה המינימום. המסקנה בדבר ההתחלה והסיום חלה על רצף מיטבי: רצף ארוך יותר יכול להתחיל או להסתיים אחרת, אם מאפשרים לחיצות עודפות.

6. הרחבה: יותר כפתורים, עדיין שתי ספרות (תרגיל 6)

בגרסת עשרת הכפתורים הקבוצות הן {0, 1, 4, 6, 7} ו־{2, 3, 5, 8, 9}. בכל קבוצה יש 5² = 25 קודים, ועוד קוד אחד בין הקבוצות. בסך הכול 2 × 25 + 1 = 51 קודים תקפים, ולכן לפחות 52 לחיצות. קודים כמו 01 תקפים: הקוד הוא רצף סימנים, לא מספר.

גם כאן מסלול אוילר מתחיל ב־7 ומסתיים ב־2: ל־7 שש יציאות וחמש כניסות; ל־2 שש כניסות וחמש יציאות. בשאר הצמתים יש שוויון. משלימים מעגל בכל קבוצה ומחברים ביניהם באמצעות 72, ולכן החסם ניתן להשגה.

בכלליות, כשבכל אחת משתי קבוצות זרות יש m כפתורים, כל זוג מתוך אותה קבוצה תקף, ויש קוד תקף יחיד מהראשונה לשנייה:

לכל צומת בתוך קבוצה m כניסות ו־m יציאות, כולל הלולאה. הקשת בין הקבוצות מוסיפה עודף יציאה במקורה ועודף כניסה ביעדה. בכל קבוצה יש מעגל אוילר; משלבים אותם עם הקשת המחברת כדי להשיג את החסם. הטיעון תקף גם כאשר בכל קבוצה כפתור אחד.

גם כשיש 201 קודים, אין צורך לרשום אותם אחד־אחד. עקרון הכפל סופר את הקודים; תנאי המסלול ומבנה הגרף מראים איך להשיג את החסם.

בדיקת הבנה

1. איך יודעים באיזו ספרה צריך להתחיל כדי להגיע למינימום?
2. מדוע שימוש מוקדם מדי ב־72 מונע השגת החסם?
3. מדוע 33 בדיקות אינן בהכרח בדיקה של 33 קודים תקפים שונים?
4. איזה חלק בפתרון מוכיח שאי אפשר בפחות לחיצות, ואיזה חלק מוכיח שאפשר?