גרף G=(V,E) מכוון, ובו n צמתים הממוספרים מ־1 ועד n, הוא גרף "מיוחד" אם מתקיימים בו התנאים האלה:
i % 2 == 0 יוצאת קשת אל צומת Vi+1.i % 2 == 1 ו-i != n יוצאת קשת לצומת Vi+1 וקשת לצומת Vi+2.דוגמה: הגרף G5 (ציור של מחומש עם קשתות פנימיות וחיצוניות לפי הכללים).
תארו גרף "מיוחד" בעבור הגרף G1, שבו צומת אחד, ובעבור הגרף G7, שבו 7 צמתים: לכל גרף רשמו את רשימת הקשתות שלו (כל קשת כזוג סדור של צמתים, למשל (1,2)).
(1) מה תהיה דרגת הכניסה ודרגת היציאה של הצומת בגרף "מיוחד", שבו צומת אחד? נמק. (2) מה תהיה דרגת הכניסה ודרגת היציאה של הצומת Vn בגרף "מיוחד" Gn, שבו n צמתים, ו־n>1? נמק.
מה מספר הקשתות בגרף "מיוחד", שבו n צמתים (כפונקציה של n)? נמק.
בעבור הגרף G5 שבדוגמה, הציגו עץ פורש מינימלי לרוחב (BFS): רשמו את קשתות העץ (כל קשת כזוג סדור של צמתים) ואת סדר גילוי הצמתים.
גרף G=(V,E) מכוון, ובו n צמתים הממוספרים מ־1 ועד n, הוא גרף "מיוחד" אם מתקיימים בו התנאים האלה:
i % 2 == 0 יוצאת קשת אל צומת Vi+1.i % 2 == 1 ו-i != n יוצאת קשת לצומת Vi+1 וקשת לצומת Vi+2.דוגמה: הגרף G5 (ציור של מחומש עם קשתות פנימיות וחיצוניות לפי הכללים).
תארו גרף "מיוחד" בעבור הגרף G1, שבו צומת אחד, ובעבור הגרף G7, שבו 7 צמתים: לכל גרף רשמו את רשימת הקשתות שלו (כל קשת כזוג סדור של צמתים, למשל (1,2)).
(1) מה תהיה דרגת הכניסה ודרגת היציאה של הצומת בגרף "מיוחד", שבו צומת אחד? נמק. (2) מה תהיה דרגת הכניסה ודרגת היציאה של הצומת Vn בגרף "מיוחד" Gn, שבו n צמתים, ו־n>1? נמק.
מה מספר הקשתות בגרף "מיוחד", שבו n צמתים (כפונקציה של n)? נמק.
בעבור הגרף G5 שבדוגמה, הציגו עץ פורש מינימלי לרוחב (BFS): רשמו את קשתות העץ (כל קשת כזוג סדור של צמתים) ואת סדר גילוי הצמתים.