Question

mst

יהא G=(V,E)G = (V,E) גרף פשוט, לא מכוון וקשיר עם פונקציית משקל w:ERw:E \to \mathbb{R}.

הציעו אלגוריתם המכריע האם ל-GG יש עפ"מ יחיד.

1

Answers

אלגוריתם:

  • מצא עפ"מ TT
  • צבע את כל שאר הקשתות בצהוב
  • מצא עפ"מ צהוב ביותר TT'
  • החזר של-GG יש עפ"מ יחיד אמ"מ TT' לא מכיל קשת צהובה

נכונות: אם ל-GG יש יותר מעפ"מ אחד אז יש לו עפ"מ שונה מ-TT ולכן קיים עפ"מ עם קשת צהובה אחת לפחות. מצד שני אם ל-GG קיים רק עפ"מ אחד אז T=TT' = Tולכן אין ב-TT' אף קשת צהובה.

סיבוכיות: מציאת עפ"מ ×\times 2 + צביעה של הקשתות - O(ElogV)O(|E|\log|V|).

1
Feedback