שאלה 6 במסלול אלגוריתמים.

גרף "כוכב סגור" — Gn — הוא גרף לא מכוון שמורכב ממעגל של n קודקודים (מ-1 עד n), המכונים "קודקודי המעגל", ומקודקוד נוסף — 0, המכונה "קודקוד מרכז" — שנמצא במרכז המעגל ומחובר לכל אחד מ"קודקודי המעגל" (כך שסך הכול יש n+1 קודקודים בגרף). מספר "קודקודי המעגל" גדול מ-2 (כלומר n > 2).

"קשתות המעגל" הן הקשתות שמחברות את "קודקודי המעגל" זה לזה. "קשתות מרכזיות" הן הקשתות שמחברות את "קודקוד מרכז" לכל אחד מ"קודקודי המעגל".

דוגמה — הגרף G6 שבעמוד 14:

             1
        6         2

             0

        5         3
             4

cycle edges  (6): 1-2, 2-3, 3-4, 4-5, 5-6, 6-1
centre edges (6): 0-1, 0-2, 0-3, 0-4, 0-5, 0-6

הסעיפים: א(1) דרגות, א(2) מספר הקשתות, א(3) האם הגרף דו-צדדי; ב — מספר העפ"מים כאשר משקל "קשתות המעגל" 2 ומשקל "הקשתות המרכזיות" 1; ג — משקלים כלליים b למעגל ו-m למרכז.

G6: מעגל קודקודים 1-2-3-4-5-6-1, וקודקוד מרכזי 0 מחובר לכל אחד מהם (6 קשתות מעגל + 6 קשתות מרכזיות = 12 קשתות, 7 קודקודים).

        1
     6     2
        0
     5     3
        4
cycle edges: 1-2,2-3,3-4,4-5,5-6,6-1; center edges: 0-1,0-2,0-3,0-4,0-5,0-6