קוגרף

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

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

הגדרה
נגדיר באופן רקורסיבי:
 קודקוד בודד הוא קוגרף
 אם  ו- הם קוגרפים זרים בקודקודים אז כך גם 
 אם  קוגרף אז כך גם  (הגרף המשלים).

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

קישורים חיצוניים
 קוגרף באתר MathWorld


קטגוריה:תורת הגרפים