Question

mst
min_cut

יהא G=(V,E)G = (V,E) גרף לא מכוון וקשיר עם משקלות על הקשתות. תהא eEe' \in E ו-kk מספר טבעי.

הציעו אלגוריתם המכריע האם ניתן לשנות את משקלן של kk קשתות כלשהן, השונות מ-ee', בגרף כך שלאחר השינוי קיים עפ"מ של GG המכיל את ee'.

1

Answers

אלגוריתם: (ללא הוכחה)

נסמן e=(u,v)e' = (u,v)

  1. הסר מהגרף את כל הקשתות עם משקל גדול או שווה לזה של ee'.
  2. מצא חתך uvuv עם מינימום קשתות והחזר קיים אמ"מ גודל החתך קטן מ-kk
1
Feedback