Question

spring_18_a
p_np

תזכורת: גרף לא מכוון, G=(V,E)G = (V,E) הוא גרף דו צדדי עם ניתן לחלק את VV לשתי קבוצות זרות C,DC, D כך שלכל קשת ב-EE מתקיים שצד אחד שלה ב-CC והשני ב-DD.

הערה: בסעיפים הבאים ניתן להניח כי כל הגרפים קשירים.

בהנחה ש-P̸=NP\text{P} \neq \text{NP}, קבעו לכל אחת מהשפות הבאות האם היא ב-P\text{P} או שהיא NP\text{NP}-שלמה.

1. }\}GG הוא גרף דו צדדי לא מכוון וקיים ב-GG מעגל המילטוני L1={G:L_1 = \{G :

רמז: בהינתן גרף GG, צרו גרף GG' אשר קבוצת צמתיו מתקבלת מהחלפת כל צומת vVv \in V בארבעה צמתים v1,v2,v3,v4v_1, v_2, v_3, v_4, כך ש-GG' דו צדדי ומתקיים ש-v1,v3Cv_1, v_3 \in C ו-v2,v4Dv_2, v_4 \in D.

בהינתן גרף דו צדדי לא מכוון, G=(CD,E)G = (C \cup D, E), נאמר ש-GG הוא גרף מרכזים אם לכל צומת vDv \in D דרגתו היא בדיוק 2.

2. }\}GG הוא גרף מרכזים וקיים ב-GG מעגל המילטוני L2={G:L_2 = \{G :

3. }\}GG הוא גרף מרכזים וקיים ב-GG מעגל העובר בכל צומת ב-CC בדיוק פעם אחת L3={G:L_3 = \{G :

1

Answers

1. עבור גרף לא מכוון, G=(V,E)G = (V, E), נגדיר את הגרף הבא:G=(VlV1V2Vr,F)G' = (V_l \cup V_1 \cup V_2 \cup V_r, F) כאשר:

Vl={vl}vVV_l = \{v_l\}_{v \in V}, V1={v1}vVV_1 = \{v_1\}_{v \in V},V2={v2}vVV_2 = \{v_2\}_{v \in V},Vr={vr}vVV_r = \{v_r\}_{v \in V}

ו-

F={ulvr:uvE}{vlv1,v1v2,v2vr}vVF = \{u_lv_r : uv \in E\} \cup \{v_lv_1, v_1v_2, v_2v_r\}_{v \in V}.

נשים לב שבלי הגבלת הכלליות בכל מעגל המילטוני ב-GG' הצמתים vl,v1,v2,vrv_l, v_1, v_2, v_r מופיעים בסדר זה במעגל, עבור כל vVv \in V. ומכאן ש-v1vnv^1 \dots v^n מעגל המילטוני ב-GG אמ"מ vl1v11v21vr1vlnv1nv2nvrnv^1_lv^1_1v^1_2v^1_r \dots v^n_lv^n_1v^n_2v^n_r מעגל המילטוני ב-GG'.

לסיום, נשים לב ש-GG' גרף דו צדדי עבור C=VlV2C = V_l \cup V_2 ו-D=V3VrD = V_3 \cup V_r.

2. נשים לב ש:

  • בגרף דו צדדי סכום דרגות הצמתים בכל צד זהה.
  • תנאים הכרחים לקיום מעגל המילטוני בגרף דו צדדי הם
    • מספר הצמתים בכל צד זהה
    • דרגת כל צומת בגרף היא לפחות 2

מכאן שבגרף מרכזים קיים מעגל המילטוני אמ"מ הוא מעגל, ולכן L2PL_2 \in \text{P}.

3. עבור גרף לא מכוון, G=(V,E)G = (V, E), נגדיר את גרף המרכזים הבא: H=(VE,F)H = (V \cup E, F) כאשר

F={{v,uv},{u,uv}}uvEF = \{\{v, uv\}, \{u, uv\}\}_{uv \in E}.

קל לראות ש-v1,v2,,vn1,vnv_1, v_2, \dots, v_{n - 1}, v_n מעגל המילטוני ב-GG אמ"מ v1,v1v2,v2,,vn1,vn1vn,vnv_1, v_1v_2, v_2, \dots, v_{n - 1}, v_{n - 1}v_{n}, v_n מעגל שעובר בכל צומת ב-VV בדיוק פעם אחת, ולכן L3/PL_3 \notin \text{P}.

1
Feedback