קוגרף

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

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

הגדרה

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

• קודקוד בודד הוא קוגרף
• אם G₁ ו-G₂ הם קוגרפים זרים בקודקודים אז כך גם $G_{1}\cup G_{2}$
• אם G קוגרף אז כך גם ${\bar {G}}$ (הגרף המשלים).

תכונות

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

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

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

• קוגרף באתר MathWorld
• קוגרף, באתר MathWorld (באנגלית)   

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

23771010קוגרף