גרפים וממפות
הוצג| English | משמעות |
|---|---|
| graph/ɡræf/ | גרף |
| vertices/ˈvɜːtɪsiːz/ | קודקודים |
| edges/ˈedʒɪz/ | קשתות |
| degree/dɪˈɡriː/ | דרגה |
| path/pæθ/ | מסלול |
| cycle/ˈsaɪkl/ | מחזור |
| connected/kəˈnektɪd/ | קשור |
| tree/triː/ | עץ |
| weighted graph/ˈweɪtɪd ɡræf/ | גרף משוקל |
| shortest path/ˈʃɔːtɪst pæθ/ | מסלול קצרך |
דגם חיבור זקוק להנחות שלו
- גרף מכיל קודקודים ו-קשרים. החלט מה הם מייצגים והאם הקשרים הם ממוסמים, משוקלים או לא ממוסמים.
- הדף עובדה משתמש בגרפים פשוטים, בלתי מכוונים וסופיים ללא לולאות או קצוות כפולים. מיקום הציור אינו משנה את הקשרים, אך חץ או משקל על קצה יכול לשנות את המודל המתמטי.
ספורו קשרים באופן אחיד
- דרגה סופרת קצוות השואפים לקודקוד בגרף פשוט ובלתי מכוון. הדרגה הכוללת שווה פי שניים למספר הקצוות, ולכן היא חייבת להיות זוגית.
- מסלול עוקב אחר הקשרים; לולאה חוזרת לנקודת ההתחלה מבלי לחזור על קודקודים אחרים. גרף הוא מחובר כאשר כל קודקוד ניתן להשגה מכל קודקוד אחר.
בגרף פשוט בלתי מכוון ללא לולאות, ארבעה קשרים נפגשים בקודקוד. מהו הדרגה שלו?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
הדרגה היא 4, מספר הקשרים המגיעים לקודקוד לפי הקונבנציה הגרפית המופיעה בשאלה.
עץ דורש שתי תכונות
- עץ הוא מחובר ואינו מכיל לולאות. עץ סופי עם n קודקודים מכיל n-1 קצוות.
- העובדה שיש n פחות 1 קשתות אינה מגדירה עץ: משולש עם רכיב נפרד בעל שני קודקודים ישנם חמישה קודקודים וארבע קשתות אך הגרף לא מקוון ומכיל מחזור.
עץ בעל 4 קודקודים. כמה קשרים יש לו?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
עץ סופי עם ארבעה קודקודים מכיל n − 1 = 3 קשרים. ספירה זו מתבססת על כך שהגרף הוא אמנם מחובר ולא מכיל מחזוריות.
במפה מחוברת בלתי מכוונה עם עלויות קשרים חיוביות מוחלט, מדוע תת-מפה מחוברת מינימלית בעלת עלות שמכסה את כל הקודקודים אינה מכילה מחזור?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
הסרת כל קשר ממחזור שומר על ההתחברות ומפחיתה את העלות הכוללת משום שמשקלו חיובי מוחלט. לכן, תת-מפה עם מחזורים לא יכולה להיות מינימלית בהנחות אלו.
כבישי חיבור בעלות חיובית. ברשת מחוברת עם עלויות כבישים חיוביות במיוחד, הסרת קצה מהלולאה משאירה את החיבורות ומנמיכה את העלות. לכן, תת-גרף חיבור בעלות מינימום הוא עץ. כדי למצוא עץ כיסוי מינימלי, יש לבחור קצוות המחברים את כל הקודקודים ללא לולאה; בחירה עיוורת ב-n-1 הקצוות הזולים ביותר עלולה להשאיר רכיבים נפרדים.
מסלול קצר הוא לא עץ כיסוי
- גרף משוקל מקנה ערך מצוין לכל קצה. מסלול קצר מינימיזי את משקל המסלול בין הקודקודים הנתונים.
- עץ כיסוי מינימלי במקום זאת מחבר כל קודקוד במשקל כולל מינימלי. מסלול קצר עשוי להיות בעל יותר קצוות ממסלול ישיר יקר; יש לסכם את המשקלים ולא לספור את הקצוות.
התאם כל מצב למה שצריך להיות הקודקודים והקשרים שלו.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
החלטה על מה הקודקודים מייצגים היא שלב המודל, והיא גם המקום שבו נוספים הנקודות.
קצה סגור משנה אפשרותיות. בדף 4.5 מוצאים מסלול בעל משקל 7, לאחר מכן סוגרים קצה ובוחנים החלפה בעלת משקל 9. אל תשתמשו בשוב בסך הישן עבור מסלול שאינו קיים עוד.
שני ציורים שנראים שונים חייבים להיות גרפים שונים.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
מפרסים שונים יכולים להיות בעלי אותה תאימות מסומנת. השווה גם כיוונים ומשקלים כאשר הם חלק מגרף המוגדר.
השוו את כל המבנים הרלוונטיים לשאלה: התאמת קודקודים, שכנות, כיוונים ומשקלים כפי שצוין. תמונות שנראות זהות אינן חייבות לייצג את אותו גרף; פריסות שונות יכולות לייצג אותם קשרים מסומנים.