משתמש:Itaybr5/בעיית כיסוי קודקודים

במדעי המחשב, בעיית כיסוי הקודקודים היא בעיה NP-שלמה בתורת הסיבוכיות.

תיאור הבעיה

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

הקודקודים {1,3,5,6} ו-{1,2,4} מהווים כיסוי קודקודים של גרף זה.

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

הגדרת הבעיה

בעיית כיסוי הקודקודים היא זו: האם, בהינתן גרף נתון $\ G=(V,E)$ ומספר טבעי $\ k$, קיים לגרף כיסוי קודקודים שמכיל לכל היותר $\ k$ צמתים? (השאלה האם קיים כיסוי קודקודים מגודל כלשהו היא טריוויאלית, כי ניתן תמיד לבחור בתור כיסוי את כל קודקודי הגרף).

ניתן להראות כי הבעיה היא NP-שלמה על ידי רדוקציה מבעיית SAT.

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

עבור כיסוי בקודקודים C ושידוך M כלשהם, כל קשת $e\in M$ חייבת לגעת לפחות באחד מן הקודקודים בכיסוי, וכל שתי קשתות שונות ב M לא יכולות לגעת באותו קודקוד מ C ולכן מקבלים ש $|M|\leq |C|$. זה גורר שגודל הכיסוי המינימלי בגרף הוא לכל הפחות גודל השידוך מקסימום בגרף. משפט קוניג (König's theorem) אומר שבגרף דו צדדי גודל הכיסוי המינימלי שווה לגודל שידוך מקסימום, שידוך מקסימום שייך למחלקת סיבוכיות p - בעיות שניתנות לפיתרון בזמן יעיל, ולכן ניתן למצוא את הכיסוי המינימלי בגרף דו צדדי (Bipartite) בזמן פולונומיאלי - זמן יעיל.

מציאת קירוב

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

סט C של כיוסי הקודקודים נבנה בדרך זו: נניח שקצה קשת e אינו מכוסה על ידי C; אז M ∪ {e} הוא התאמה וגם e ∉ M, זו סתירה לההנחה כי M הוא מקסימאלי. כיסוי אופטימלי מכיל נקודות קצה לפחות אחד מכל קצה בM; בסך הכל, הסט C הוא לכל היותר גדול פי 2 מכיסוי הקודקודים האופטימלי, וזהו הקירוב הטוב ביותר הידוע כיום. אלגוריתם זה התגלה ע"י Fanica Gavril ו - Mihalis Yannakakis.

פסאודו קוד (מאנגלית: Pseudo-Code)

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

פסאודו קוד לאלגוריתם קירוב הנ"ל:

APPROXIMATION-VERTEX-COVER(G):
C = ∅
E'= G.E

while E'≠ ∅:
    let (u, v) be an arbitrary edge of E'
    C = C ∪ {u, v}
    remove from E' every edge incident on either u or v

return C

NP-שלמות

מחלקת NP בהנחה ש-P ≠ NP

במדעי המחשב, NP היא מחלקת סיבוכיות חשובה של בעיות אלגוריתמיות, שכוללת את הבעיות שבהינתן פתרון מוצע כלשהו לבעיה, קל לבדוק אם הוא אכן מהווה פתרון ("קל" במובן של סיבוכיות זמן ריצה "סביר" של אלגוריתם האימות). המחלקה NP כוללת אלפי בעיות הנחקרות במסגרת מדעי המחשב. במסגרת קטגוריית בעיות זו, כל בעיה ניתנת לרידוקציה לאחרת, כלומר מציאת פתרון יעיל לאחת הבעיות תביא לפתון יעיל לכל הבעיות בקטגוריה זו. השאלה אם קל גם למצוא פתרון לבעיות במחלקה בזמן "סביר", ידועה כשאלה "האם P=NP"; שאלה זו היא אחת מהבעיות הפתוחות המרכזיות במדעי המחשב, ואחת מ"שבע בעיות המילניום" של מכון קליי למתמטיקה, שהכריז על פרס בסך מיליון דולר שיוענק למי שיפתור את הבעיה‏‏.

ראו גם

• NP (מחלקת סיבוכיות)
• סיבוכיות זמן
• פסאודו קוד

הערות שוליים

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