קבוצה שולטת

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

חסמים[עריכת קוד מקור | עריכה]

יהי G גרף בעל n ≥ 1 צמתים ותהי Δ הדרגה המקסימלית של הגרף. ידוע כי:

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

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ 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