קבוצה שולטת

בתורת הגרפים, קבוצה שולטת בגרף (G(V,E היא תת-קבוצה D של הצמתים ב-V כך שכל צומת שאינו ב-D מחובר בקשת לפחות לצומת אחד ב-D. דרגת השליטה (γ(G בגרף היא מספר הצמתים הקטן ביותר המהווים קבוצה שולטת בגרף. בעיית הקבוצה השולטת היא בעיה NP-קשה (יותר מכך היא בעיה NP-שלמה), הבודקת בהינתן גרף כלשהו ומספר K, האם קיימת קבוצה שולטת קטנה מ-K.

בעיית הקבוצה השולטת נחקרה החל משנת 1950 אך החלה למשוך תשומת לב מחוקרים בתחום בעיקר החל משנות ה-70. בשנת 1988 היה ידוע על יותר מ-800 מאמרים בנושא שרובם עסקו באלגוריתמים למציאת דרגת השליטה במחלקות מסוימות של גרפים.

חסמים
יהי G גרף בעל n ≥ 1 צמתים ותהי Δ הדרגה המקסימלית של הגרף. ידוע כי:
 מכיוון שכל צומת יכול לשלוט על Δ צמתים לכל היותר, דרגת השליטה של הגרף (γ(G חסומה מלמטה על ידי (n/(1+Δ. כלומר (γ(G) ≥ n/(1+Δ.
 קבוצת כל הצמתים V בגרף היא קבוצה שולטת. כלומר γ(G) ≤ n.
 אם הגרף קשיר אזי קיימות לפחות שתי קבוצות שולטות זרות לחלוטין בגרף. לכן, בכל גרף קשיר γ(G) ≤ n/2.

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

הערות שוליים

קטגוריה:תורת הגרפים
קטגוריה:בעיות NP-שלמות