קוגרף

מתוך ויקיפדיה, האנציקלופדיה החופשית

בתורת הגרפים, קוגרף הוא גרף הנוצר מקודקודים בודדים על ידי הפעלות של איחוד זר ואופרטור הגרף המשלים (גרף שיש בו קשת אםם אין קשת בגרף המקורי).

דוגמאות לקוגרפים הם גרפים מלאים וגרפי טורן.

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

נגדיר באופן רקורסיבי:

  • קודקוד בודד הוא קוגרף
  • אם G1 ו-G2 הם קוגרפים זרים בקודקודים אז כך גם
  • אם G קוגרף אז כך גם (הגרף המשלים).

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

היותו של גרף קוגרף שקולה לתכונות הבאות:

  • הגרף לא מכיל את המסילה מאורך 3 כתת-גרף מושרה
  • כל תת-גרף מושרה מקיים שכל קליקה מקסימלית וכל קבוצה בלתי תלויה מקסימלית נחתכות בקודקוד יחיד
  • בכל תת-גרף מושרה עם לפחות 2 קודקודים יש שני קודקודים עם אותם שכנים
  • כל צביעה חמדנית של כל תת-גרף מושרה היא אופטימלית

קישורים חיצוניים[עריכת קוד מקור | עריכה]