CS计算机代考程序代写 DNA algorithm Network Flow Some Applications

Network Flow Some Applications
2021-03-03 CSC373 Winter 2021 – Sam Toueg 1

Bipartite Matching (brief recap of Monday’s lecture)
2021-03-03 CSC373 Winter 2021 – Sam Toueg 2

Bipartite Matching to Max Flow
Lemma: ∃ matching of size ” in # ⟺ ∃ integral flow of value ” in F
Corollary: Maximum Matching in # = Max Flow in F
& = [(-, .), 0]
&’ #(
!” =1for every edge ”
F= &′,),*,! &’
#( !
”
)$) %* %*
$
2021-03-03 CSC373 Winter 2021 – Sam Toueg
3

Min Vertex Cover
2021-03-03 CSC373 Winter 2021 – Sam Toueg 5

Vertex Cover
• # = (1, 3): undirected graph
• vertex cover (VC): a subset 1′ of the nodes of # that “touches’’ every edge of #, i.e., every edge has at least one endpoint in 1′
• minimum vertex cover: a VC with minimum size
2021-03-03 CSC373 Winter 2021 – Sam Toueg 6

By Hustvedt – Own work, CC BY-SA 3.0, h;ps://commons.wikimedia.org/w/index.php?curid=3466036
VC was also used to model the elimination of repetitive DNA sequences for synthetic biology and metabolic engineering applications.
!
!
!
!
!
Fewest cameras to cover all streets or bldg hallways
2021-03-03 CSC373 Winter 2021 – Sam Toueg 7

Vertex Cover Claim1:Foranymatching7in#,andanyVC8of#, 7 ≤ 8
Proof: Follows from
• Every edge in 7 must be covered by at least one node in 8
• No node in 8 can cover more than one edge of 7
If a node covers two edges of 2 …
Then 2 is not a matching!
2021-03-03 CSC373 Winter 2021 – Sam Toueg 9

Vertex Cover Claim1:Foranymatching7in#,andanyVC8of#, 7 ≤ 8
Claim2:Foranymatching7in#,andanyVC8of#,if 7 = 8 :
• 7 is a maximum matching
• 8 is a minimum VC
Proof:
Let 7 be any matching of # and 8 be any VC of # Let7∗ beamaxmatchingof#and8∗ beaminVCof#
2021-03-03 CSC373 Winter 2021 – Sam Toueg 10

Vertex Cover for Bipartite Graph
Claim 3: If # = [ .,/ ,3] is a biparJte graph then: |max matching of #| = |min VC of #|
Proof: Given a biparJte graph # construct a flow network F as before Let > be a max integral flow in F (it exists by the FF algorithm)
./
&’
./
&’
#( #( !
)$) %* %*
! ” =1foralledge” 2021-03-03 CSC373 Winter 2021 – Sam Toueg
”
$
16

Vertex Cover for Bipartite Graph Claim 3: If # = [ .,/ ,3] is a biparJte graph then:
|max matching of #| = |min VC of #|
Proof: Let > be a max integral flow in F (it exists by the FF algorithm) Let ? = nodes reachable from @ in #4 , and A = 1 − ?
Recall: (“, $) is an s-t min-cut, so &'( “, $ = *’+(,) [max-flow = min-cut] Consider the type of edges in F from ? to A:
?
!
(1)
.
/
(1) @ → . ∩ A
(2) /∩? →D
(3) .∩? →(/∩A)
Fact: no edges of type (3) in F ! ”
-∩7
(3)
A
.∩7
(2)
-∩6
.∩6
2021-03-03
CSC373 Winter 2021 – Sam Toueg 17

Vertex Cover for Bipar7te Graph
Fact: There are no edges of type (3) in F
Claim 3.1 (a): 8 = (. ∩ A) ∪ (/ ∩ ?) is a min VC of #
Proof:
edge type:
covered by nodes in:
.∩7
Ø – has 4 types of edges: ./✅
By Fact, no such edges – ∩ 6 [and . ∩ 6]
-∩6
✅ ✅
?✅
!
(1)
A ”
-∩7
.∩7
(2)
-∩6
.∩6
2021-03-03 CSC373 Winter 2021 – Sam Toueg
18

?
!
Vertex Cover for Bipar7te Graph Fact: There are no edges of type (3) in F
Claim 3.1 (a): 8 = (. ∩ A) ∪ (/ ∩ ?) is a min VC of # ./
-∩7
.∩7
A ”
-∩6
.∩6
2021-03-03
CSC373 Winter 2021 – Sam Toueg 19

Vertex Cover for Bipar7te Graph Fact: There are no edges of type (3) in F
Claim 3.1 (b): 8 = (. ∩ A) ∪ (/ ∩ ?) is a min VC of # Proof:
# type (1) edges
# type (2) edges
./ ! (1)-∩7 .∩7
(2)
+ = @∩6 = )’3 4, 6
A ”
+ |(D∩4)|
?
= 0’1 2
= |max matching in /|
bcs: “,$ is a min-cut and % is max-flow
by previous lecture: max-flow = size of
a maximum matching
-∩6
.∩6
So + =|.|forsomematching.of/ By Claim 2: + is a min VC (Phew!)
2021-03-03
CSC373 Winter 2021 – Sam Toueg 20

? !
./
(3)
Vertex Cover
Fact: There are no edges of type (3) in flow network F
Proof:
Suppose, for contradicJon, ∃(G,H) s.t., G ∈ . ∩ ? and H ∈ / ∩ A (a)> G,H =0or(b)> G,H =1
Case(a):>G,H =0⇒#4hastheedgeG→H
⇒ H is reachable from @ in #4 ⇒ H ∈ ?, contradicts H ∈ A
-∩7 8
.∩7
A ”
-∩6
9 .∩6
2021-03-03
CSC373 Winter 2021 – Sam Toueg 21

Vertex Cover
Fact: There are no edges of type (3) in flow network F
Proof:
Suppose, for contradiction, ∃(G, H) s.t., G ∈ . ∩ ? and H ∈ / ∩ A (a)> G,H =0or(b)> G,H =1
Case(b):>G,H =1(∗)
Since . ∈ “, . is reachable from 0 in -&
Let 1: 0 → . simple path in -&
Subcase 1: 1 = (0, .) ; so the edge (0, .) is in -&
? !
./
(3)
So:,0,. =0 (∗∗)
[bcsif, 0,. =1,edge(0,.)isnotin-&]
(∗) and ∗∗ ⇒ a violation of flow conservation at .:
A !→G→H
-∩7 8
.∩7
-∩6
9 .∩6
”
01
2021-03-03
CSC373 Winter 2021 – Sam Toueg
22

Vertex Cover
Fact: There are no edges of type (3) in flow network F
Proof:
Suppose, for contradicJon, ∃(G,H) s.t., G ∈ . ∩ ? and H ∈ / ∩ A (a)> G,H =0or(b)> G,H =1
Case(b):>G,H =1(∗)
Since . ∈ “, . is reachable from 0 in -&
Let 1: 0 → . simple path in -&
Subcase2:I:!→G! →H! →G” →H” →G# →⋯→G$ →H$ →G
? !
∈ 7 (reachable from ) in &!) ./FFRFRFRFR
Note that:
• /% hasreverseedgeH$ →G⇒2 G,H$ =1
-∩7 8
.∩7
(3)
• By ∗,2G,H =1
9″ ∈ 7
violation of flow conservation at 8!
9∈6
A ”
So we have:
* 1 (
1 ‘! 1’
-∩6
9 .∩6
2021-03-03
CSC373 Winter 2021 – Sam Toueg
24

Vertex Cover Algorithm for Bipar7te Graphs
BIPARTITE-VC(#): Input#=[1= .,/,3] construct flow network F from # S(T + V)
>←MaxFlow(F) S TWX ,hereX=V⇒S(TWV)
? ← nodes reachable from @ in #4
A←1−?
8←(.∩A)∪(/∩?) S(V) return 8
RunningJme: S(TWV)
• Fact: for general graphs, finding a min VC is NP-Complete
• What about finding a max matching for general graphs?
Ø Can be done with polynomial-Jme algorithms!
2021-03-03 CSC373 Winter 2021 – Sam Toueg 25
S(V + T)

Hall’s Theorem
on
Perfect Bipartite Matching
2021-03-03 CSC373 Winter 2021 – Sam Toueg 1

Hall’s Theorem
Perfect matching in a bipartite graph ! = ([%, ‘], )) !”
$%
!
“‘
#(
)* ## 22
perfect matching:
every node is matched to another node
&
2021-03-03
CSC373 Winter 2021 – Sam Toueg 2

Hall’s Theorem
Perfect matching in a bipar0te graph ! = ([%, ‘], )) !”
$%
!
“‘
#(
)* ## 22
perfect matching: (%, ‘) (*, +) (,, -) (., /) (0, 1) every node is matched to another node
&
2021-03-03
CSC373 Winter 2021 – Sam Toueg 3

Hall’s Theorem
Perfect matching in a bipar0te graph ! = ([%, ‘], ))
!”!
$%
!
“‘
#(
)* ## 22
!′⊆ !
size 2
” $%
4 !!
size 1
&
!& “c
(
Is a perfect matching possible here? No: % and * can be matched only to ‘
Clearly: perfect matching is impossible if there is a subset !′⊆ ! such that
!′ > |, !! |, where , !! are the neighbors of !′
2021-03-03 CSC373 Winter 2021 – Sam Toueg 4
#

Hall’s Theorem
Perfect matching in a bipar0te graph ! = ([%, ‘], ))
!”!
$%
!
“‘
#(
)* ## 22
Bipar0te graph ! = ([%, ‘], )) has no perfect matching
” $%
!& “c
(
Is a perfect matching possible here? No: % and * can be matched only to ‘
&
#
⟺∃%′⊆%,s.t, %5 >|1 %5 | 2021-03-03 CSC373 Winter 2021 – Sam Toueg 5

Hall’s Theorem
Bipar0te graph ! = ([%, ‘], )) has no perfect matching
⟺∃%′⊆%,s.t, %5 >|1 %5 | Because: a matching for %′ implies %′ has at least |%5| neighbors!
Proof: (⟸) Straigh:orward
2021-03-03 CSC373 Winter 2021 – Sam Toueg 6

Hall’s Theorem
Bipar0te graph ! = ([%, ‘], )) has no perfect matching
⟺∃%′⊆%,s.t, %5 >|1 %5 | Proof: (⟹) Assume no perfect matching for ! exists.
So: maxmatchingin4 <∩6 Because: " • !∩7+!!=# " • !∩7 + "∩7 = 7 <# (c) > :# ≤ <∩6 by(a) ## 22 !! >|4!!|
Because:
• There is no !! ⟷ “′ edge (otherwise: 7 would not be a vertex cover!) • So4!! ⊆”∩7and4!! ≤”∩7
2021-03-03 CSC373 Winter 2021 – Sam Toueg 7

Edge-Disjoint Paths
2021-03-03 CSC373 Winter 2021 – Sam Toueg 1

Edge-Disjoint Paths
Two ! ⤳ # paths $ and $′ are edge-disjoint if they don’t share an edge
& !#'”
(
%
2021-03-03
CSC373 Winter 2021 – Sam Toueg 2
$

Edge-Disjoint Paths
Two ! ⤳ # paths $ and $′ are edge-disjoint if they don’t share an edge
& !#'”
(
%
2021-03-03
CSC373 Winter 2021 – Sam Toueg 3
$

Edge-Disjoint Paths
Two ! ⤳ # paths $ and $′ are edge-disjoint if they don’t share an edge
& !#'”
(
%
2021-03-03
CSC373 Winter 2021 – Sam Toueg 4
$

Edge-Disjoint Paths
• edge = communication link
• 2 edge-disjoint paths
⇒ 2 independent ways to send a message from ! to #
⇒ single link failure will not prevent communication from ! to #
Two ! ⤳ # paths $ and $′ are edge-disjoint if they don’t share an edge
& !#'”
(
%
2021-03-03
CSC373 Winter 2021 – Sam Toueg 5
$

Edge-Disjoint Paths
• Problem
ØInput: directed graph ‘ = ),+ ; !,# ∈ )
ØOutput: find a max-size set of edge-disjoint ! ⤳ # paths
Two ! ⤳ # paths $ and $′ are edge-disjoint if they don’t share an edge
& !#'”
(
%
2021-03-03
CSC373 Winter 2021 – Sam Toueg 6
$

Edge-Disjoint Paths
• Problem
ØInput: directed graph ‘ = ),+ ; !,# ∈ )
ØOutput: find a max-size set of edge-disjoint ! ⤳ # paths
(1) From ‘, construct a flow network F as follows:
• delete edges into ! and edges out of #
• all remaining edges have capacity 1
(2) Find integral max flow in F (= max # of edge-disjoint ! ⤳ # paths) (3) Decompose flow into edge-disjoint paths (will see how later)
Theorem:
There are 0 edge-disjoint ⟺ There is an integral flow ! ⤳ # paths in ‘ of value 0 in F
2021-03-03 CSC373 Winter 2021 – Sam Toueg 8

Edge-Disjoint Paths
Theorem:
There are 0 edge-disjoint ⟺ There is an integral flow ! ⤳ # paths in ‘ of value 0 in F
Proof: (0 edge−disjoint paths ⟹ 8low of value 0)
• •
Let $!,…,$” be 0 edge-disjoint ! ⤳ # paths
Define the following flow A:
ØAB =1ifB∈$!∪⋯∪$”and0otherwise
Ø A saOsfies capacity constraints because 0 ≤ A B Ø A saOsfies flow conservaOon because otherwise:
1111 1)1 )1
111
≤ 1
2021-03-03 CSC373 Winter 2021 – Sam Toueg
9

Edge-Disjoint Paths
Theorem:
There are 0 edge-disjoint ⟺ There is an integral flow ! ⤳ # paths in ‘ of value 0 in F
Proof: (0 edge−disjoint paths ⟹ 8low of value 0)
• •
Let $!,…,$” be 0 edge-disjoint ! ⤳ # paths
Define the following flow A:
ØAB =1ifB∈$!∪⋯∪$”and0otherwise
Ø A saOsfies capacity constraints because 0 ≤ A B Ø A saOsfies flow conservaOon because otherwise:
path1 1 1 1 1)1 )1
111
≤ 1
2021-03-03 CSC373 Winter 2021 – Sam Toueg
10

Edge-Disjoint Paths
Theorem:
There are 0 edge-disjoint ⟺ There is an integral flow ! ⤳ # paths in ‘ of value 0 in F
Proof: (0 edge−disjoint paths ⟹ 8low of value 0)
• •
Let $!,…,$” be 0 edge-disjoint ! ⤳ # paths
Define the following flow A:
ØAB =1ifB∈$!∪⋯∪$”and0otherwise
Ø A satisfies capacity constraints because 0 ≤ A B Ø A satisfies flow conservation because otherwise:
path1 1 1 1 1)1 )1
path 1 1 1 2021-03-03 CSC373 Winter 2021 – Sam Toueg
≤ 1
11

Edge-Disjoint Paths
Theorem:
There are 0 edge-disjoint ⟺ There is an integral flow ! ⤳ # paths in ‘ of value 0 in F
Proof: (0 edge−disjoint paths ⟹ 8low of value 0)
• •
Let $!,…,$” be 0 edge-disjoint ! ⤳ # paths
Define the following flow A:
ØAB =1ifB∈$!∪⋯∪$”and0otherwise
Ø A saOsfies capacity constraints because 0 ≤ A B Ø A saOsfies flow conservaOon because otherwise:
path1 1 1 1
≤ 1
path?1 ) 1
path 1 1
) 1 1
2021-03-03 CSC373 Winter 2021 – Sam Toueg
12

Edge-Disjoint Paths
Theorem:
There are 0 edge-disjoint ⟺ There is an integral flow ! ⤳ # paths in ‘ of value 0 in F
Proof: (0 edge−disjoint paths ⟹ 8low of value 0)
• •
Let $!,…,$” be 0 edge-disjoint ! ⤳ # paths
Define the following flow A:
ØAB =1ifB∈$!∪⋯∪$”and0otherwise
Ø A saOsfies capacity constraints because 0 ≤ A B Ø A saOsfies flow conservaOon because otherwise:
path1 1 1 1 path?1 ) 1 ) 1
≤ 1
path 1 1
1
Impossible: path shares an edge with path or 2021-03-03 CSC373 Winter 2021 – Sam Toueg
13

Edge-Disjoint Paths
Theorem:
There are 0 edge-disjoint ⟺ There is an integral flow ! ⤳ # paths in ‘ of value 0 in F
Proof: (0 edge−disjoint paths ⟹ 8low of value 0)
• •
Let $!,…,$” be 0 edge-disjoint ! ⤳ # paths
Define the following flow A:
ØAB =1ifB∈$!∪⋯∪$”and0otherwise
Ø A saOsfies capacity constraints because 0 ≤ A B Ø A saOsfies flow conservaOon because otherwise:
path1 1 1 1
≤ 1
path?1 ) 1
path 1 1
) 1 1
2021-03-03 CSC373 Winter 2021 – Sam Toueg
14

Edge-Disjoint Paths
Theorem:
There are 0 edge-disjoint ⟺ There is an integral flow ! ⤳ # paths in ‘ of value 0 in F
Proof: (0 edge−disjoint paths ⟹ 8low of value 0)
• •
Let $!,…,$” be 0 edge-disjoint ! ⤳ # paths
Define the following flow A:
ØAB =1ifB∈$!∪⋯∪$”and0otherwise
Ø A saOsfies capacity constraints because 0 ≤ A B Ø A saOsfies flow conservaOon because otherwise:
≤ 1
path1 1 1 1
1 path
path? 1 ) 1 path 1
)
1
1
2021-03-03
CSC373 Winter 2021 – Sam Toueg
15

Edge-Disjoint Paths
Theorem:
There are 0 edge-disjoint ⟺ There is an integral flow ! ⤳ # paths in ‘ of value 0 in F
Proof: (0 edge−disjoint paths ⟹ 8low of value 0)
• •
Let $!,…,$” be 0 edge-disjoint ! ⤳ # paths
Define the following flow A:
ØAB =1ifB∈$!∪⋯∪$”and0otherwise
Ø A satisfies capacity constraints because 0 ≤ A B
Ø A satisfies flow conservation because otherwise:
path 1 1 1
)
1 path
1 path
1
≤ 1
path? 1 ) 1 path 1
1
2021-03-03
CSC373 Winter 2021 – Sam Toueg
16

Edge-Disjoint Paths
Theorem:
There are 0 edge-disjoint ⟺ There is an integral flow ! ⤳ # paths in ‘ of value 0 in F
Proof: (0 edge−disjoint paths ⟹ 8low of value 0)
• •
Let $!,…,$” be 0 edge-disjoint ! ⤳ # paths
Define the following flow A:
ØAB =1ifB∈$!∪⋯∪$”and0otherwise
Ø A saOsfies capacity constraints because 0 ≤ A B
Ø A saOsfies flow conservaOon because otherwise:
≤ 1
path 1 1 1 ) 1
1 1 path
) 1path
1
Impossible: path shares an edge with path or
path 1 2021-03-03
CSC373 Winter 2021 – Sam Toueg
1 path?
17

Edge-Disjoint Paths
Theorem:
There are 0 edge-disjoint ⟺ There is an integral flow ! ⤳ # paths in ‘ of value 0 in F
Proof: (0 edge−disjoint paths ⟹ 8low of value 0)
• •
Let $!,…,$” be 0 edge-disjoint ! ⤳ # paths
Define the following flow A:
ØAB =1ifB∈$!∪⋯∪$”and0otherwise
Ø A saOsfies capacity constraints
Ø A saOsfies flow conservaOon
Ø ! has 0 outgoing edges (one for each $# ), each with flow 1 Ø So A is an integral flow of value 0
2021-03-03 CSC373 Winter 2021 – Sam Toueg 18

Edge-Disjoint Paths
Theorem:
There are 0 edge-disjoint ⟺ There is an integral flow ! ⤳ # paths in ‘ of value 0 in F
Proof: (0 edge−disjoint paths ⟸ 8low of value 0)
• Let A be an integral flow of value 0 in the flow network F
• Recall: in F the capacity of each edge is 1
• ⇒ ! must have 0 outgoing edges with a flow of 1 each
• Pick one such edge !, Q and “go to’’ Q
• By flow conservaOon, Q must have at least one outgoing edge with flow of 1 (which we haven’t used up yet)
• Pick one such edge Q, R and “go to’’ R
• ConOnue building this path from ! unOl you hit #
• Repeat this for each of the other 0 − 1 edges from ! with flow 1
⇒ this gives 0 edge-disjoint ! ⤳ # paths in ‘
19

Edge-Disjoint Paths Edge-Disjoint-Paths (‘, !, #):
construct flow network F from ‘ U(W + Y) A←MaxFlow(F) FFalgo:U Y[\ ,here\=W⇒U(Y[W)
$ ← Path-Decomposition(A) return $
RunningOme: U(Y[W)
U(W + Y)
2021-03-03 CSC373 Winter 2021 – Sam Toueg 20

Edge-Disjoint Paths
Path-Decomposi9on(A): $←∅
whileR^_ A >0do Q ← !; a^#h ← ! while Q ≠ # do
$ : integral flow in F (every edge has capacity 1)
U(W+Y) R←anynodeRsuchthatA Q,R =1 a^#h ← a^#h ∘ R
AQ,R ←0
Q←R
$ ← $ ∪ a^#h
return $ 2021-03-03
Running 9me: U(W + Y)
CSC373 Winter 2021 – Sam Toueg 21

Related Posts