קבוצה בלתי תלויה (תורת הגרפים)

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

קבוצה בלתי תלויה היא קבוצת קודקודים בגרף, אשר אין זוג מביניהם המחוברים ישירות דרך קשת אחת.

שאלת קיום קבוצה כזו מסדר k היא בעיית NP-שלמה.

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.