Question

spring_04_a
matching
greedy

שאלה זו מתייחסת למונחים הבאים:

  • שידוך בגרף לא מכוון G=(V,E)G = (V, E) הוא קבוצת קשתות MEM \subseteq E כך שבכל צומת vVv \in V פוגעת קשת אחת מ-MM לכל היותר.
  • MM הוא שידוך מקסימלי אם לא קיים שידוך שמכיל אותו ממש.
  • MM הוא שידוך מקסימום אם לא קיים שידוך גדול ממנו.

א. נתון גרף לא מכוון G=(V,E)G = (V,E) (שימו לב שהגרף אינו דו צדדי בהכרח). הציעו אלגוריתם בסיבוכיות זמן O(V+E)O(|V| + |E|) המחשב שידוך מקסימלי ב-GG. הוכיחו נכונות ונתחו סיבוכיות.

ב. נתון גרף לא מכוון G=(V,E)G = (V, E). יהא MM שידוך מקסימלי ב-GG ויהא MM^* שידוך מקסימום ב-GG. הוכיחו כי M2M|M^*| \leq 2|M|.

ג. הראו גרף לא מכוון G=(V,E)G = (V, E) עבורו קיימים שידוך מקסימלי MM ושידוך מקסימום MM^* כך ש-M=2M|M^*| = 2|M|.

1

Answers

א. האלגוריתם: נעבור על כל הקשתות בסדר כלשהו ונוסיף כל קשת שאפשר.

סיבוכיות: עוברים על כל הקשתות פעם אחת, את הבדיקה אפשר לעשות ב-O(1)O(1) על ידי סימון הצמתים שבשידוך ובסך הכל O(V+E)O(V + E).

ב. אם M<MM < M^* אז קיימת קשת קשת uvMuv \in M^* כך שגם uu וגם vv לא מכוסים על ידי MM ולכן MM לא מקסימלי.

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

tikz
1
Feedback