用破圈法和避圈法求下图的最小树。[img=199x107]17940565ec48f35.png[/img]
给题图中的顶点和边编号[tex=0.786x1.0]a0JAwcjYC8oKg4ygp76dXg==[/tex]和[tex=0.786x1.071]7tqE5ZceH5PZa3J1RF9rtw==[/tex]，如下图所示[img=237x121]1794057dd9da59e.png[/img]1 采用避圈法。按照图中的边的权的大小，依次从小到大逐步选取边，并使之不构成圈，直到不能选取时，经过九次选取后，得到的边集合[tex=11.643x1.357]b53FulBYTt/3S4JpIyxsfcuEG82PQRPDzn7it8XZARpM7GgYj4ouJJF7jXeZ+MRGsfOSGKH/sivFPNztmK520dSi4Y8ko8B4Dh6ufX2iqRo=[/tex]构成的图即为题图的一个最小支撑树，如下图所示，此支撑树的权为19.[img=216x118]179405ab5a2f150.png[/img]2 采用破圈法。应用破圈原理，经过七次破圈，去掉了权数较大的七条边：[tex=7.357x1.0]RwvW8yCoUp2Mk0mTMUMKLErqZPMldhrOXVbRueCMbO+dFkcFD8pR86cYarnfS1Ca[/tex]和[tex=1.214x1.0]kX/rrqF5y+0kUP7jWjFxxw==[/tex]而余下的边集合[tex=11.643x1.357]b53FulBYTt/3S4JpIyxsfcuEG82PQRPDzn7it8XZARqUJTsGNUZdw1Xk0vw3jpo8grb2ArHTtT1h8tHocDg48pUdzMPSTXyngXLnfBEAD8U=[/tex]构成了一个无圈的图即为题图的另一个最小支撑8树，如下图所示。此支撑树的权仍然为19。这说明，题图的最小支撑树不惟一，但其总权均为19.
举一反三
内容
- 0
避圈法和破圈法都可以求得最小树。（ ）
- 1
最小树可用破圈法或避圈法求得。
- 2
最小树的求解方法,避圈法和破圈法计算结果相同。
- 3
避圈法和破圈法都可以求得最小树。（ ） A: 对 B: 错
- 4
最小树的求解方法,避圈法和破圈法计算结果相同。(<br/>)