א. הטענה לא נכונה, למשל עבור GG' הבא כאשר הצומת השמאלי הוא הצומת החדש:

ב.

טענה: קיים עפ"מ של GG' שמוכל ב-TET \cup E', כאשר EE' היא קבוצת הקשתות שנוגעות ב-vv, הצומת החדש.

הוכחה: על שאר הקשתות ניתן להפעיל את הכלל האדום.

אלגוריתם: הרץ את קרוסקל על TET \cup E'.

נכונות: מיידי מהטענה ומנכונות קרוסקל.

סיבוכיות: נשים לב שמספר הקשתות הוא O(V)O(V) ולכן הסיבוכיות היא O(VlogV)O(V \log V).

Feedback