קבוצה שולטת
(הופנה מהדף קבוצה שולטת (תורת הגרפים))
בתורת הגרפים, קבוצה שולטת בגרף (G(V,E היא תת-קבוצה D של הצמתים ב-V כך שכל צומת שאינו ב-D מחובר בקשת לפחות לצומת אחד ב-D. דרגת השליטה (γ(G בגרף היא מספר הצמתים הקטן ביותר המהווים קבוצה שולטת בגרף. בעיית הקבוצה השולטת היא בעיה NP-קשה (יותר מכך היא בעיה NP-שלמה), הבודקת בהינתן גרף כלשהו ומספר K, האם קיימת קבוצה שולטת קטנה מ-K.
בעיית הקבוצה השולטת נחקרה החל משנת 1950 אך החלה למשוך תשומת לב מחוקרים בתחום בעיקר החל משנות ה-70. בשנת 1988 היה ידוע על יותר מ-800 מאמרים בנושא שרובם עסקו באלגוריתמים למציאת דרגת השליטה במחלקות מסוימות של גרפים[1].
חסמים
עריכהיהי G גרף בעל n ≥ 1 צמתים ותהי Δ הדרגה המקסימלית של הגרף. ידוע כי:
- מכיוון שכל צומת יכול לשלוט על Δ צמתים לכל היותר, דרגת השליטה של הגרף (γ(G חסומה מלמטה על ידי (n/(1+Δ. כלומר (γ(G) ≥ n/(1+Δ.
- קבוצת כל הצמתים V בגרף היא קבוצה שולטת. כלומר γ(G) ≤ n.
- אם הגרף קשיר אזי קיימות לפחות שתי קבוצות שולטות זרות לחלוטין בגרף. לכן, בכל גרף קשיר γ(G) ≤ n/2.
קישורים חיצוניים
עריכה
הערות שוליים
עריכה- ^ S. T. Hedetniemi and R. C. Laskar, Bibliography on domination in graphs and some basic definitions of domination parameters, Discrete Mathematics, Volume 86, Issues 1-3, 14 December 1990, Pages 257-277