✳flâneur — a map of the web's best reading

Gomory–Hu tree - Wikipedia

en.wikipedia.org · 3,200 words · saved by 1 readers

In combinatorial optimization, the Gomory–Hu tree[1] of an undirected graph with capacities is a weighted tree that represents the minimum s-t cuts for all s-t pairs in the graph. The Gomory–Hu tree can be constructed in |V| − 1 maximum flow computations. It is named for Ralph E. Gomory and T. C. Hu. Let 𝐺 = ( 𝑉 𝐺 , 𝐸 𝐺 , 𝑐 ) be an undirected graph with 𝑐 ( 𝑢 , 𝑣 ) being the capacity of the edge ( 𝑢 , 𝑣 ) respectively. Then T is said to be a Gomory–Hu tree of G, if for each 𝑠 , 𝑡 ∈ 𝑉 𝐺 where Gomory–Hu Algorithm Using the submodular property of the capacity function c, one has 𝑐 ( 𝑋 ) + 𝑐 ( 𝑌 ) ≥ 𝑐 ( 𝑋 ∩ 𝑌 ) + 𝑐 ( 𝑋 ∪ 𝑌 ) . Then it can be shown that the minimum s-t cut in G' is also a minimum s-t cut in G for any s, t ∈ X. To show that for all ( 𝑃 , 𝑄 ) ∈ 𝐸 𝑇 , 𝑤 ( 𝑃 , 𝑄 ) = 𝜆 𝑝 𝑞 for some p ∈ P, q ∈ Q throughout the algorithm, one makes use of the following lemma, The lemma can be used again repeatedly to show that the output T satisfies th

Gomory–Hu tree - Wikipedia Jump to content From Wikipedia, the free encyclopedia Weighted tree representing s-t cuts of a graph In combinatorial optimization , the Gomory–Hu tree [ 1 ] of an undirected graph with capacities is a weighted tree that represents the minimum s - t cuts for all s - t pairs in the graph. The Gomory–Hu tree can be constructed in | V | − 1 maximum flow computations. It is named for Ralph E. Gomory and T. C. Hu . Definition [ edit ] Let G = ( V G , E G , c ) {\displaystyle G=(V_{G},E_{G},c)} be an undirected graph with c ( u , v ) {\displaystyle c(u,v)} being the capaci

Explore this link on the map →

related reading