גרף "כוכב סגור" — Gn — הוא גרף לא מכוון שמורכב ממעגל של n קודקודים (מ-1 עד n), המכונים "קודקודי המעגל", ומקודקוד נוסף — 0, המכונה "קודקוד מרכז" — שנמצא במרכז המעגל ומחובר לכל אחד מ"קודקודי המעגל" (כך שסך הכול יש n+1 קודקודים בגרף). מספר "קודקודי המעגל" גדול מ-2 (כלומר n > 2).
"קשתות המעגל" הן הקשתות שמחברות את "קודקודי המעגל" זה לזה. "קשתות מרכזיות" הן הקשתות שמחברות את "קודקוד מרכז" לכל אחד מ"קודקודי המעגל".
דוגמה — הגרף G6:
1
6 2
0
5 3
4
בגרף G6: "קשתות המעגל" — 1-2, 2-3, 3-4, 4-5, 5-6, 6-1; "קשתות מרכזיות" — 0-1, 0-2, 0-3, 0-4, 0-5, 0-6.
נתון גרף "כוכב סגור" - Gn. מה הן דרגות "קודקודי המעגל" בגרף, ומהי דרגת "קודקוד מרכז"? נמקו את תשובתכם.
כמה "קשתות מעגל" יש בגרף, וכמה "קשתות מרכזיות" יש בגרף? נמקו את תשובתכם.
האם הגרף הוא דו-צדדי? נמקו את תשובתכם.
נתון גרף ממושקל שהוא "כוכב סגור" - Gn, שבו לכל "קשתות המעגל" משקל 2, ולכל "הקשתות המרכזיות" משקל 1. כמה עפ"מים (עצים פורשים מינימליים) שונים יש בגרף? נמקו את תשובתכם.
נתון גרף ממושקל שהוא "כוכב סגור" - Gn, שבו לכל "קשתות המעגל" משקל b (גדול מ-0), ולכל "הקשתות המרכזיות" משקל m (גדול מ-0). הציבו ערכים ל-b ול-m, שעבורם כל מסלול קצר (קל) בין שני "קודקודי מעגל" יעבור דרך "קודקוד מרכז". נמקו את תשובתכם.
נתון כי b = 10. מהו הערך הגדול ביותר של m שבעבורו כל מסלול קצר (קל) בין שני "קודקודי מעגל" עדיין יעבור דרך "קודקוד מרכז"? נמקו את תשובתכם.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.