גרף מיתרי

בתורת הגרפים, גרף מיתרי הוא גרף שבו כל מעגל באורך 4 או יותר מכיל מיתר, שהוא צלע המחברת בין שני צמתים לא-רצופים במעגל. בניסוח אחר, G הוא גרף מיתרי אם אין לו תת גרף מושרה שהוא מעגל באורך 4 או יותר.

משפחת הגרפים המיתריים היא תת-משפחה של הגרפים המושלמים.

צמתים סימפליקליים וסדר הסרה מושלם

צומת סימפליקלי (simplicial) הוא צומת שקבוצת השכנים שלו מהווה קליקה. גרף מיתרי תמיד מכיל קדקד סימפליקלי ‏ ‏. למעשה, גרף מיתרי הוא או קליקה או שהוא מכיל לפחות שני צמתים סימפליקליים שאינם שכנים.

סדר הסרה מושלם (perfect elimination ordering) של גרף, הוא פרמוטציה $\pi$ של קדקדי הגרף כך שלכל קדקד $v$ מתקיים כי $v$ והשכנים של $v$ שמופיעים לאחריו ב-$\pi$ מהווים קליקה. כלומר, $\pi= \left\langle v_1,v_2,\cdots,v_n \right\rangle$ הוא סדר הסרה מושלם אם לכל $1\leq i \leq n$ מתקיים כי הצומת $v_i$ הוא סימפליקלי בתת הגרף המושרה על $\{v_i,v_{i+1},\cdots,v_n\}$.

משפט: גרף הוא מיתרי אם ורק אם יש לו סדר הסרה מושלם. ‏

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

אלגוריתמים יעילים לגרפים מיתריים

גרפים מיתריים הם בפרט מושלמים וככאלה, יש מגוון של בעיות שניתנות לפתרון בזמן פולינומי על גרפים מיתריים. אלא שאלגוריתמים אלו אינם בעלי אופי קומבינטורי, אלא מבוססים על תכנון לינארי ואלגוריתם האליפסואידים. עבור גרפים מיתריים, ידועים אלגוריתמים קומבינטוריים יעילים מאוד. להלן מספר אלגוריתמים יעילם עבור בעיות שידועות כ-NP-קשה על גרפים כלליים. אלגוריתמים אלו מסתמכים על כך שלגרף מיתרי קיים סדר הסרה מושלם. ‏

קליקה מקסימאלית

בהינתן גרף מיתרי $G$ עם סדר הסרה מושלם $\pi= \left\langle v_1,v_2,\cdots,v_n \right\rangle$, אזי לפי ההגדרה לכל צומת $v_i$ מתקיים כי $v_i$ ביחד עם השכנים שלו שמופיעים אחריו ב-$\pi$, מהווים קליקה. אם כן, האלגוריתם סורק את צמתי הגרף וכאשר הוא מטפל בצומת $v_i$ הוא סופר את מספר השכנים של $v_i$ אשר מופיעם אחריו ב-$\pi$, ובוחר את הקליקה הגדולה ביותר מבין כל אלו שנסרקו.

צביעה של גרף מיתרי

בהינתן גרף מיתרי $G$ עם סדר הסרה מושלם $\pi=\left\langle v_i,v_{i+1},\cdots,v_n \right\rangle$, האלגוריתם סורק את צמתי הגרף בסדר הפוך (כלומר מתחיל ב-$v_n$ ומסיים ב-$v_1$), וצובע את צמתי הגרף באופן חמדני. ביתר פירוט- כאשר האלגוריתם מטפל בצומת $v_i$ הוא צובע אותו בצבע $k$ המינימאלי כך שאף אחד משכניו של $v_i$ אינו צבוע בצבע שמספרו $k$. קל לראות שאלגוריתם זה מוביל לצביעה במספר מינימאלי של צבעים. נניח בשלילה שלא כך הוא, ונתבונן בגרף מיתרי $G$ ובפעם הראשונה שהאלגוריתם משתמש ביותר צבעים מאשר המינימום ההכרחי. כעת, מאחר ו-$G$ מיתרי, הוא בפרט מושלם ולכן מספר הצביעה של $G$ (כלומר המספר המינימאלי של צבעים שבאמצעותם ניתן לצבוע את $G$) הוא בדיוק כגודל הקליקה המקסימלית ב-$G$. אבל אז, משמעות הדבר היא שבחרנו עבור צומת כלשהו את הצבע המינמאלי שאינו בשימוש על ידי אף אחד משכניו, ומספר זה גדול יותר מאשר גודל הקליקה המקסימאלית ב-$G$. זה כמובן לא ייתכן, כי מספר שכניו בהכרח קטן (בלפחות 1) מגודל הקליקה המקסימאלית.

ראו גם

• גרף מושלם
• גרף קטעים

לקריאה נוספת

• Martin Charles Golumbic, Algorithmic graph theory and perfect graphs, Elsevier, 1980.