בעיית כיסוי קודקודים

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

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

תיאור הבעיה[עריכת קוד מקור | עריכה]

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

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

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

הגדרת הבעיה[עריכת קוד מקור | עריכה]

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

Vertex-cover.svg

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

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

Minimum-vertex-cover.svg


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

מציאת קירוב[עריכת קוד מקור | עריכה]

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

Vertex-cover-from-maximal-matching.svg

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

פסאודו קוד (מאנגלית: Pseudo-Code)[עריכת קוד מקור | עריכה]

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

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

 1 APPROXIMATION-VERTEX-COVER(G):
 2 C = 
 3 E'= G.E
 4 
 5 while E'≠ :
 6     let (u, v) be an arbitrary edge of E'
 7     C = C  {u, v}
 8     remove from E' every edge incident on either u or v
 9 
10 return C

[1] [2]


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

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

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

ראו גם[עריכת קוד מקור | עריכה]


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

  1. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2013). Introduction to Algorithms. Delhi: PHI Learning Pvt. Ltd. עמ' 1109. 
  2. ^ Chakrabarti, Amit. "Approximation Algorithms: Vertex Cover". http://www.cs.dartmouth.edu/. בדיקה אחרונה ב-21 בפברואר 2005. 
  3. ^ 7 בעיות המילניום, אתר מכון קליי למתמטיקה