I know


2009 年 10 月 2 日  星期五   晴天

Brief Proof on Bottleneck Spanning Tree 分類: Programming Impossib...

Brief Proof on Bottleneck Spanning Tree

[Homework for Introduction to Algorithms, Exercise 23-3]




A bottleneck spanning tree (T) of an undirected graph G is a spanning tree of G whose largest edge weight is the minimum one over all spanning trees of G.  We say that the value of the bottleneck spanning tree is the weight of the maximum-weight edge in T.


A Minimum Spanning Tree (MST) is a Bottleneck Spanning Tree, and the one with the smallest cost.

[Brief Proof]

Consider a Minimum Spanning Tree (A) of Graph G, whose set of sub graphs contain another spanning tree B that is a bottleneck spanning tree, while MST (A) isn't.

First, without lost of generality, suppose e(u, v) in A is the edge with the largest weight in the MST with no ties, whose weight is W(u, v). Then, consider deleting e(u, v) from A, separating the tree into two trees, namely U and V respectively.

Then we construct a set of edges, S, that for each edge (ui, vi), where ui is a vertex in U and vi in V, suffices (ui, vi)S. One may notice that there exists at least one edge (uj, vj)S which is in the Bottleneck Spanning Tree (B). (Otherwise B is not a spanning tree.)

So, as B is the Bottleneck Spanning Tree while A isn’t, each edge e(x, y) in B suffices e(x, y) < W(u, v). Suppose we have edge e(x,y) in S,  replace it with edge e(u,v) in A will make A a Spanning Tree with a even smaller sum of weights. Here we find a contradiction.


訪客留言 (返回 phoeagon 的日誌)

CesWeme 於 2017-03-30 05:12 PM 發表:
Tadalista [url=]Generic Kamagra Online[/url] Where To Buy Nizagara Kamagra In Deutschland [url=]Order Lasix[/url] Wirkung Von Viagra 100 Mg Cialis Generico Barato [url=]Amoxil Pills[/url] Cephalexin For Veternarian Use Fda Category Listing For Keflex [url=]Comprare Lasix[/url] Levitra Ou Cialis Forum Get Macrobid Cod Accepted [url=]Cheapest Inderal[/url] Levitra Flushing Buy Lipitor Online With No Prescription [url=]Dapoxetine Priligy Buy[/url] Propecia Tuenti Wholesale Viagra 100mg [url=]Cytotec 100mcg[/url] Buy Bactrim Online Overnight Delivery Levitra Sotto Lingua [url=]Pharmacy Propecia[/url] Viagra 50mg Wirkung Buy Prevacid Odt [url=]Deltasone Tablet[/url] Cialis Without Prescription Overnight Dapoxetine Approbation De La Fda [url=]Lasix Tablets[/url] Achat Amoxicillin Pharmacie Vente Achat
[ 回覆 ] [ 封鎖 ] [ 刪除 ]

Coach Outlet 於 2012-08-22 09:02 AM 發表:

Coach Outlet Online

the Diaoyu Islands to the death, one banner said. Another said, “Even if China is covered with graves, we must kill

Coach Outlet Online

all Japanese.” Another photograph showed a handwritten sign taped to the entrance of Suning, a popular electronics store,

Coach Outlet Online

telling customers it was no longer selling Japanese products. Some protests appear to have turned violent. According

Coach Outlet Online

to several postings, demonstrators on Sunday attacked sushi restaurants or other businesses perceived to have a Japanese

Coach Outlet Online

connection. Several photographs said to be from Shenzhen, across the border from Hong Kong, showed what appeared to be damaged or overturned cars — most of them Japanese models — as well as several police

Gucci Belts

vehicles. The demonstrations appeared to be sanctioned and chaperoned by the police, who generally prohibit public protests unless they

Gucci Belts

suit the needs of the Communist Party. In the past, Beijing has allowed nationalist sentiment to bubble up into street demonstrations, but

Louis Vuitton Belts

the authorities usually keep them contained out of concern they might spiral out of control or turn into popular antigovernment sentiment. Even as the protests began unfolding Sunday morning, a group of conservative

Coach Outlet

Japanese activists might have planted the seeds for further anger in China. About 10 of the activists, including local assembly

Coach Outlet

members from Tokyo, swam ashore to the disputed island, Uotsuri. While Japan controls the island chain, the Tokyo government restricts

Coach Factory Outlet

access to avoid inflaming regional tensions. The 10 who landed Sunday did so without permission, and were later questioned by the Japanese Coast Guard. Members of the group said they were responding to the pro-China activists’ landing, and they

Coach Outlet Online

urged Prime Minister Yoshihiko Noda to do more to defend the islands.
[ 回覆 ] [ 封鎖 ] [ 刪除 ]

COACHOUTLET 於 2012-08-21 03:37 PM 發表:
that will happen to boost his roster for the playoff push."Not too compelling or interesting," said Sabean, suspended for

Coach Outlet Online

Saints sounding terms coaches

Coach Outlet Online

Will Smith has been

Coach Outlet

who made several late-
[ 回覆 ] [ 封鎖 ] [ 刪除 ]

cheelye 於 2011-01-04 02:10 PM 發表:
thanks for sharing ur Brief , yeah, i dont understand too
[ 回覆 ] [ 封鎖 ] [ 刪除 ]

katherine816 於 2009-10-04 03:45 AM 發表:
[ 回覆 ] [ 封鎖 ] [ 刪除 ]

電郵地址: (不會公開)
驗證碼:  按此更新驗證碼 (如看不清楚驗證碼請點擊圖片刷新)
俏俏話: (必需 登入 後才能使用此功能)
[ 開啟多功能編輯器 ]

暱稱: phoeagon
性別: 男
« February 2018 »
» 最新日誌
Blog Moved!
Twitter Fav列表达陈100...
» 日誌分類
全部 (175)
Code Storage (11)
Math&Phy@Chem@MM (8)
Music Anyway (5)
Programming Impossible (28)
RSS提示 (2)
StorageBox (5)
'Bout Here (12)
滑鼠人生 (42)
碎屑 (51)
未分類 (11)
» 訪客留言
buy generic ... (Viagrasr)
buy generic ... (Viagrasr)
viagra gener... (Viagrasr)
viagra gener... (Viagarasr)
» 最近訪客
» 每月文章
» 日誌訂閱
» 我的好友
» 我的連結
Ink Mark --Jlim
» 日誌統計
文章總數: 175
留言總數: 75
今日人氣: 11
累積人氣: 69376
» 站內搜索
RSS Feed