מעגל (תורת הגרפים)

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
מעגל (תורת הגרפים)
Undirected 6 cycle.svg
גרף מעגל באורך 6
מספר צמתים n
מספר קשתות n
אוטומורפיזם (2n (Dn
מספר צבעי צומת 2 אם זה גרף זוגי
3 אם זה גרף אי זוגי
מספר צבעי קשת 2 אם זה גרף זוגי
3 אם זה גרף אי זוגי
תכונות גרף קשיר

גרף רגולרי
מסלול אוילרי
מסלול המילטוני
גרף דו-צדדי

סימון Cn

בתורת הגרפים, מעגלאנגלית: Cycle graph או Circular graph) הוא גרף המורכב ממסלול לא-ריק שמתחיל ומסתיים באותו צומת.

באופן פורמלי, מעגל הוא גרף המורכב מקשתות \ v_0,\dots,v_{n-1} כך שלכל i, הקשתות \ v_i, v_{i+1 \pmod{n}} נפגשות בצומת משותף, ואין צמתים משותפים אחרים.

גרף מעגל המורכב מ-\ n קשתות נקרא Cn. בגרף Cn מספר הקשתות שווה למספר הצמתים (שווה ל-\ n ) ודרגת כל צומת שווה ל-2. כלומר, מכל צומת יוצאות שתי קשתות.

טרמינולוגיה[עריכת קוד מקור | עריכה]

ישנם שמות נרדפים רבים לגרף מעגל. זה כולל גרף מעגל פשוט (simple cycle graph), גרף בעל מעגלים (cyclic graph), על אף שהשם השני אינו שכיח כיוון שהוא מתייחס בעיקר למקרים בהם גרף הוא לא גרף חסר מעגלים (acyclic graph). מעגל, פוליגון, n-gon שמות נפוצים גם כן. מעגל בעל מספר זוגי של צמתים נקרא מעגל זוגי (even cycle); מעגל בעל מספר אי-זוגי של צמתים נקרא מעגל אי-זוגי (odd cycle).

תכונות[עריכת קוד מקור | עריכה]

גרף מעגל מכוון[עריכת קוד מקור | עריכה]

גרף מעגל מכוון שאורכו 8

גרף מעגל מכוון הוא סוג של גרף מכוון שהוא גם גרף מעגל. שכל הקשתות בו מופנות לאותו כיוון.

הוצאת קבוצת הצמתים המינימלית שתהפוך את הגרף לחסר מעגלים שווה ל1. תהליך זה נקרא feedback vertex set. הוצאת קבוצת הקשתות המינימלית שתהפוך את הגרף לחסר מעגלים שווה ל1. תהליך זה נקרא feedback arc set.

בגרף זה, דרגת הכניסה שווה ל-1 ודרגת היציאה שווה ל-1.

ראו גם[עריכת קוד מקור | עריכה]