מעגל (תורת הגרפים)
גרף שמכיל מעגל אחד, ללא קשתות נוספות / ויקיפדיה האנציקלופדיה encyclopedia
בתורת הגרפים, מעגל (באנגלית: Cycle graph או Circular graph) הוא גרף המורכב ממסלול לא-ריק המתחיל ומסתיים באותו צומת, כאשר הצמתים היחידים שחוזרים על עצמם הם הצומת הראשון והצומת האחרון.
עובדות מהירות מספר צמתים, מספר קשתות ...
גרף מעגל פשוט באורך 6 | |
מספר צמתים | n |
---|---|
מספר קשתות | n |
אוטומורפיזם | (2n (Dn |
מספר צבעי צומת |
2 (גרף זוגי) 3 (אי זוגי) |
מספר צבעי קשת |
2 (גרף זוגי) 3 (אי זוגי) |
תכונות |
גרף קשיר גרף רגולרי מסלול אוילרי מסלול המילטוני גרף דו-צדדי |
סימון | Cn |
סגירה
באופן פורמלי, מעגל הוא גרף בעל צמתים , עם הקשתות .
נהוג לסמן גרף מעגל המורכב מ- קשתות כך: Cn. בגרף Cn מספר הקשתות שווה למספר הצמתים (שווה ל-) ודרגת כל צומת שווה ל-2. כלומר, מכל צומת יוצאות שתי קשתות.