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

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

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

באופן פורמלי, מעגל הוא גרף בעל צמתים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v_0,\dots,v_{n-1}} , עם הקשתות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v_i, v_{i+1 \pmod{n}}} .

נהוג לסמן גרף מעגל המורכב מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} קשתות כך: Cn. בגרף Cn מספר הקשתות שווה למספר הצמתים (שווה ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} ) ודרגת כל צומת שווה ל-2. כלומר, מכל צומת יוצאות שתי קשתות.

טרמינולוגיה

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

מעגל בעל מספר זוגי של צמתים נקרא מעגל זוגי (even cycle); מעגל בעל מספר אי-זוגי של צמתים נקרא מעגל אי-זוגי (odd cycle).

תכונות

גרף מעגל מכוון

קובץ:DC8.png
גרף מעגל מכוון שאורכו 8

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

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

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

ראו גם

קישורים חיצוניים

ויקישיתוף מדיה וקבצים בנושא מעגל בוויקישיתוף
  • מעגל, באתר MathWorld (באנגלית)
Logo hamichlol 3.png
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0