שאלה 11אלגוריתמיקה2021 קיץ מועד במסלולים קצרים ממקור יחיד (BFS)סה״כ 20 נק׳
גרפים מיוחדים - ניתוח דרגות ועצים פורשים
גרף G = (V,E) מכוון, ובו n צמתים הממוספרים מ־1 ועד n, הוא גרף "מיוחד" אם מתקיימים בו התנאים האלה:
n הוא אי־זוגי.
מכל צומת Vi שמקיים i % 2 = 0 יוצאת קשת אל צומת Vi+1.
מכל צומת Vi שמקיים i % 2 = 1 ו־i ≠ n יוצאת קשת לצומת Vi+1 וקשת לצומת Vi+2.
מצומת Vn יוצאת קשת לצומת V1.
אין קשתות נוספות מעבר לאמור לעיל.
✎ דוגמה
הגרף G5 שלפניך הוא גרף מיוחדגרף G = (V,E) מכוון, ובו n צמתים הממוספרים מ־1 ועד n, הוא גרף "מיוחד" אם מתקיימים בו התנאים האלה:
- n הוא אי־זוגי.
- מכל צומת Vi שמקיים i % 2 = 0 יוצאת קשת אל צומת Vi+1.
- מכל צומת Vi שמקיים i % 2 = 1 ו־i ≠ n יוצאת קשת לצומת Vi+1 וקשת לצומת Vi+2.
- מצומת Vn יוצאת קשת לצומת V1.
- אין קשתות נוספות מעבר לאמור לעיל.:
G5: 1->2, 1->3, 2->3, 3->4, 3->5, 4->5, 5->1
משימות
אמשימה א
תרשים25%
צייר גרף מיוחדגרף G = (V,E) מכוון, ובו n צמתים הממוספרים מ־1 ועד n, הוא גרף "מיוחד" אם מתקיימים בו התנאים האלה:
- n הוא אי־זוגי.
- מכל צומת Vi שמקיים i % 2 = 0 יוצאת קשת אל צומת Vi+1.
- מכל צומת Vi שמקיים i % 2 = 1 ו־i ≠ n יוצאת קשת לצומת Vi+1 וקשת לצומת Vi+2.
- מצומת Vn יוצאת קשת לצומת V1.
- אין קשתות נוספות מעבר לאמור לעיל. בעבור הגרף G1, שבו צומת אחד, ובעבור הגרף G7, שבו 7 צמתים.
ב(1)משימה ב(1)
תשובה12%
מה תהיה דרגת הכניסה ודרגת היציאה של הצומת Vn בגרף מיוחדגרף G = (V,E) מכוון, ובו n צמתים הממוספרים מ־1 ועד n, הוא גרף "מיוחד" אם מתקיימים בו התנאים האלה:
- n הוא אי־זוגי.
- מכל צומת Vi שמקיים i % 2 = 0 יוצאת קשת אל צומת Vi+1.
- מכל צומת Vi שמקיים i % 2 = 1 ו־i ≠ n יוצאת קשת לצומת Vi+1 וקשת לצומת Vi+2.
- מצומת Vn יוצאת קשת לצומת V1.
- אין קשתות נוספות מעבר לאמור לעיל.G1, שבו צומת אחד? נמק את תשובתך.
ב(2)משימה ב(2)
תשובה13%
מה תהיה דרגת הכניסה ודרגת היציאה של הצומת Vn בגרף מיוחדגרף G = (V,E) מכוון, ובו n צמתים הממוספרים מ־1 ועד n, הוא גרף "מיוחד" אם מתקיימים בו התנאים האלה:
- n הוא אי־זוגי.
- מכל צומת Vi שמקיים i % 2 = 0 יוצאת קשת אל צומת Vi+1.
- מכל צומת Vi שמקיים i % 2 = 1 ו־i ≠ n יוצאת קשת לצומת Vi+1 וקשת לצומת Vi+2.
- מצומת Vn יוצאת קשת לצומת V1.
- אין קשתות נוספות מעבר לאמור לעיל.Gn, שבו n צמתים, ו־n > 1? נמק את תשובתך.
גמשימה ג
תשובה25%
מה מספר הקשתות בגרף מיוחדגרף G = (V,E) מכוון, ובו n צמתים הממוספרים מ־1 ועד n, הוא גרף "מיוחד" אם מתקיימים בו התנאים האלה:
- n הוא אי־זוגי.
- מכל צומת Vi שמקיים i % 2 = 0 יוצאת קשת אל צומת Vi+1.
- מכל צומת Vi שמקיים i % 2 = 1 ו־i ≠ n יוצאת קשת לצומת Vi+1 וקשת לצומת Vi+2.
- מצומת Vn יוצאת קשת לצומת V1.
- אין קשתות נוספות מעבר לאמור לעיל.Gn, שבו n צמתים (כפונקציה של n)? נמק את תשובתך.
דמשימה ד
תרשים25%
בעבור הגרף G5 שבדוגמה, הצג עץ פורש מינימלי לרוחב (BFS).
שפת התכנות שלי
שאלה 11אלגוריתמיקה2021 קיץ מועד במסלולים קצרים ממקור יחיד (BFS)סה״כ 20 נק׳
גרפים מיוחדים - ניתוח דרגות ועצים פורשים
גרף G = (V,E) מכוון, ובו n צמתים הממוספרים מ־1 ועד n, הוא גרף "מיוחד" אם מתקיימים בו התנאים האלה:
n הוא אי־זוגי.
מכל צומת Vi שמקיים i % 2 = 0 יוצאת קשת אל צומת Vi+1.
מכל צומת Vi שמקיים i % 2 = 1 ו־i ≠ n יוצאת קשת לצומת Vi+1 וקשת לצומת Vi+2.
מצומת Vn יוצאת קשת לצומת V1.
אין קשתות נוספות מעבר לאמור לעיל.
✎ דוגמה
הגרף G5 שלפניך הוא גרף מיוחדגרף G = (V,E) מכוון, ובו n צמתים הממוספרים מ־1 ועד n, הוא גרף "מיוחד" אם מתקיימים בו התנאים האלה:
- n הוא אי־זוגי.
- מכל צומת Vi שמקיים i % 2 = 0 יוצאת קשת אל צומת Vi+1.
- מכל צומת Vi שמקיים i % 2 = 1 ו־i ≠ n יוצאת קשת לצומת Vi+1 וקשת לצומת Vi+2.
- מצומת Vn יוצאת קשת לצומת V1.
- אין קשתות נוספות מעבר לאמור לעיל.:
G5: 1->2, 1->3, 2->3, 3->4, 3->5, 4->5, 5->1
משימות
אמשימה א
תרשים25%
צייר גרף מיוחדגרף G = (V,E) מכוון, ובו n צמתים הממוספרים מ־1 ועד n, הוא גרף "מיוחד" אם מתקיימים בו התנאים האלה:
- n הוא אי־זוגי.
- מכל צומת Vi שמקיים i % 2 = 0 יוצאת קשת אל צומת Vi+1.
- מכל צומת Vi שמקיים i % 2 = 1 ו־i ≠ n יוצאת קשת לצומת Vi+1 וקשת לצומת Vi+2.
- מצומת Vn יוצאת קשת לצומת V1.
- אין קשתות נוספות מעבר לאמור לעיל. בעבור הגרף G1, שבו צומת אחד, ובעבור הגרף G7, שבו 7 צמתים.
ב(1)משימה ב(1)
תשובה12%
מה תהיה דרגת הכניסה ודרגת היציאה של הצומת Vn בגרף מיוחדגרף G = (V,E) מכוון, ובו n צמתים הממוספרים מ־1 ועד n, הוא גרף "מיוחד" אם מתקיימים בו התנאים האלה:
- n הוא אי־זוגי.
- מכל צומת Vi שמקיים i % 2 = 0 יוצאת קשת אל צומת Vi+1.
- מכל צומת Vi שמקיים i % 2 = 1 ו־i ≠ n יוצאת קשת לצומת Vi+1 וקשת לצומת Vi+2.
- מצומת Vn יוצאת קשת לצומת V1.
- אין קשתות נוספות מעבר לאמור לעיל.G1, שבו צומת אחד? נמק את תשובתך.
ב(2)משימה ב(2)
תשובה13%
מה תהיה דרגת הכניסה ודרגת היציאה של הצומת Vn בגרף מיוחדגרף G = (V,E) מכוון, ובו n צמתים הממוספרים מ־1 ועד n, הוא גרף "מיוחד" אם מתקיימים בו התנאים האלה:
- n הוא אי־זוגי.
- מכל צומת Vi שמקיים i % 2 = 0 יוצאת קשת אל צומת Vi+1.
- מכל צומת Vi שמקיים i % 2 = 1 ו־i ≠ n יוצאת קשת לצומת Vi+1 וקשת לצומת Vi+2.
- מצומת Vn יוצאת קשת לצומת V1.
- אין קשתות נוספות מעבר לאמור לעיל.Gn, שבו n צמתים, ו־n > 1? נמק את תשובתך.
גמשימה ג
תשובה25%
מה מספר הקשתות בגרף מיוחדגרף G = (V,E) מכוון, ובו n צמתים הממוספרים מ־1 ועד n, הוא גרף "מיוחד" אם מתקיימים בו התנאים האלה:
- n הוא אי־זוגי.
- מכל צומת Vi שמקיים i % 2 = 0 יוצאת קשת אל צומת Vi+1.
- מכל צומת Vi שמקיים i % 2 = 1 ו־i ≠ n יוצאת קשת לצומת Vi+1 וקשת לצומת Vi+2.
- מצומת Vn יוצאת קשת לצומת V1.
- אין קשתות נוספות מעבר לאמור לעיל.Gn, שבו n צמתים (כפונקציה של n)? נמק את תשובתך.
דמשימה ד
תרשים25%
בעבור הגרף G5 שבדוגמה, הצג עץ פורש מינימלי לרוחב (BFS).
