גרף מושלם

בתורת הגרפים, גרף מושלם הוא גרף שבו בכל תת גרף מושרה, גודל הקליקה המקסימלית שווה למספר הצביעה של תת-הגרף.

צביעה חוקית של גרף G היא בפרט גם צביעה חוקית של כל תת-גרף שלו, לכן אם קיימת ב -G קליקה בגודל k אז כל צביעה חייבת להשתמש בלפחות k צבעים. מכאן שגודל הקליקה המקסימלית מהווה חסם תחתון על מספר הצביעה של הגרף. אם חסם זה הוא הדוק לכל תת-גרף מושרה של G, אז G נחשב מושלם.

משפחות של גרפים מושלמים

1. גרפים מלאים - כל תת-גרף מושרה של גרף מלא הוא בעצמו גרף מלא ולכן הן מספר הצביעה שלו והן גודל הקליקה המקסימלית המוכלת בו הם כמספר הצמתים בו.
2. גרפים דו צדדיים – גרפים בעלי מספר צביעה 2. כל תת-גרף מושרה של גרף דו צדדי או שאינו מכיל אף צלע (ואז כל קליקה מכילה צומת יחיד וכן ניתן לצבוע את כל הצמתים באותו צבע, כלומר מספר הצביעה של תת-הגרף הוא 1) או שהוא מכיל צלעות, אבל אינו מכיל אף קליקה עם יותר משני צמתים (ואז מספר הצביעה הוא 2, כגודל הקליקה המקסימלית).
3. גרפים מיתריים – גרפים בהם לכל מעגל באורך 4 לפחות קיים מיתר, או לחלופין לא קיים בהם תת-גרף מושרה שהוא מעגל מאורך 4 לפחות.
4. גרפי השוואה של סדר חלקי – אלו גרפים אשר ניתן לכוון את הקשתות שלהם כך שהיחס שהן יוצרות יהיה יחס סדר חלקי.
5. גרפי קטעים – גרפים אשר ניתן להתאים בין הצמתים שלהם לבין קטעים על הישר באופן כזה ששני צמתים מחוברים בקשת אם ורק אם הקטעים המתאימים להם נחתכים.

מאפיינים של גרפים מושלמים

המשפט החלש של הגרף המושלם: (לובאס): G הוא גרף מושלם אם ורק אם המשלים של G הוא מושלם.

המשפט החזק של הגרף המושלם: G הוא גרף מושלם אם ורק אם G והמשלים של G לא מכילים תת-גרף מושרה שהוא מעגל באורך אי זוגי מגודל 5 לפחות. השערה זו הייתה פתוחה במשך שנים רבות עד שהוכחה על ידי צ'ודנובסקי, רוברטסון, סימור ותומאס ב-2006^[1].

אלגוריתמים בגרפים מושלמים

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

גם בעיית הזיהוי של גרפים מושלמים הייתה פתוחה שנים רבות, אולם לאחר הוכחת המשפט החזק של הגרף המושלם נמצא לה אלגוריתם פולינומי^[2].

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

• גרף מושלם, באתר MathWorld (באנגלית)

הערות שוליים

1. Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). "The strong perfect graph theorem". Annals of Mathematics 164 (1): 51–229.
2. Chudnovsky, Maria; Cornuéjols, Gérard; Liu, Xinming; Seymour, Paul; Vušković, Kristina (2005). "Recognizing Berge graphs". Combinatorica 25: 143–186.