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