---
# System prepended metadata

title: HW10 - Q2
tags: [109-2, 演算法]

---

# HW10 - Q2
###### tags: `演算法`, `109-2`

:::success
https://hackmd.io/@Cing-Chen/HkZHm80du
:::

## Question
**Exercises 23.1-11:**
Given a graph G and a minimum spanning tree T, suppose that we decrease the weight of
one of the edges not in T. Give an algorithm for finding the minimum spanning tree in the
modified graph

## Mein Answer
有圖、有MST，把一個不在 MST 的 edge 的 weight 調低，問新 MST

![](https://i.imgur.com/7BxGomR.png)

步驟如下
1. 把調低 edge 的那條 edge 連同他的 vertex 一起加進原本 MST 圖
2. 利用這張圖計算新的 MST

<!-- ![](https://i.imgur.com/WvyJuvi.png) -->

![](https://i.imgur.com/eRaStqf.png)

準備好了
![](https://i.imgur.com/5AZOsk1.png)

我們把最顯眼的 2021 調低成 7 吧
![](https://i.imgur.com/NXvmgJN.png)

把那條 edge 塞到原本的 MST
![](https://i.imgur.com/l1LQmU1.png)

算出 MST
![](https://i.imgur.com/oSq3Fka.png)

以上。

### PseudoCode
```c
push effected vertex to mst
FindMST(mst)
```
![](https://i.imgur.com/7wQt277.png)


## Tool used
- https://graphonline.ru/