הצגת המקור של הדף "קוגרף"

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

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

==הגדרה==
נגדיר באופן [[רקורסיה|רקורסיבי]]:
* קודקוד בודד הוא קוגרף
* אם <math>G_1</math> ו-<math>G_2</math> הם קוגרפים זרים בקודקודים אז כך גם <math>G_1 \cup G_2</math>
* אם <math>G</math> קוגרף אז כך גם <math>\bar{G}</math> (הגרף המשלים).

==תכונות==
היותו של גרף קוגרף שקולה לתכונות הבאות:
* הגרף לא מכיל את המסילה מאורך 3 כתת-גרף מושרה
* כל תת-גרף מושרה מקיים שכל [[קליקה (תורת הגרפים)|קליקה]] מקסימלית וכל קבוצה בלתי תלויה מקסימלית נחתכות בקודקוד יחיד
* בכל תת-גרף מושרה עם לפחות 2 קודקודים יש שני קודקודים עם אותם שכנים
* כל [[גרף n-צביע|צביעה]] חמדנית של כל תת-גרף מושרה היא אופטימלית

==קישורים חיצוניים==
* [http://mathworld.wolfram.com/Cograph.html קוגרף] באתר [[MathWorld]]
* {{MathWorld}}


{{קצרמר|מתמטיקה}}
[[קטגוריה:תורת הגרפים]]