Discrete Optimization: Fundamentals and Applications
Discrete Optimization
MA2827
Fondements de l’optimisation discrète
Slides courtesy of M. Pawan Kumar
•
Lecture 1
–
Graph preliminaries
–
Complexity basics
–
Shortest path algorithms (Dijkstra, Bellman-Ford,
Floyd-Warshall)
•
Lecture 2
–
Chow-Liu tree
–
Minimum spanning tree (Prim’s, Kruskal’s)
–
Maximum flow (Ford-Fulkerson, Dinits)
Recap of previous lectures
•
Preliminaries
•
Menger’s Theorem for Disjoint Paths
•
Path Packing
Outline
But first
…
Find the max flow/min cut.
Show the steps.
•
Preliminaries
•
Menger’s Theorem for Disjoint Paths
•
Path Packing
Outline
Directed Graphs (Digraphs)
v
1
v
0
v
2
v
6
v
4
v
5
v
3
‘n’ vertices or nodes V
‘m’ arcs A: ordered pairs from V
D = (V, A)
Indegree of a Vertex
Number of arcs entering the vertex.
indeg(v
0
) = 1, indeg(v
1
) = 1, indeg(v
4
) = 2, …
D = (V, A)
v
1
v
0
v
2
v
6
v
4
v
5
v
3
Indegree of a Subset of Vertices
Number of arcs entering the subset.
indeg({v0
,v
1
}) = 1, indeg({v1
,v
4
}) = 3, …
D = (V, A)
v
1
v
0
v
2
v
6
v
4
v
5
v
3
Outdegree of a Vertex
Number of arcs leaving the vertex.
outdeg(v
0
) = 1, outdeg(v
1
) = 1, outdeg(v
2
) = 2, …
D = (V, A)
v
1
v
0
v
2
v
6
v
4
v
5
v
3
Outdegree of a Subset of Vertices
Number of arcs leaving the subset.
outdeg({v0
,v
1
}) = 1, outdeg({v1
,v
4
}) = 2, …
D = (V, A)
v
1
v
0
v
2
v
6
v
4
v
5
v
3
s-t Path
Sequence P = (s=v
0
,a
1
,v
1
,…,a
k
,t=v
k
), a
i
= (v
i-1
,v
i
)
D = (V, A)
v
1
v
0
v
2
v
6
v
4
v
5
v
3
Vertices s=v
0
,v
1
,…,t=v
k
are distinct
S-T Path
S and T are subsets of V
D = (V, A)
v
1
v
0
v
2
v
6
v
4
v
5
v
3
Any st-path where s
S and t
T
S
T
S-T Path
S and T are subsets of V
D = (V, A)
v
1
v
0
v
2
v
6
v
4
v
5
v
3
Any st-path where s
S and t
T
S
T
•
Preliminaries
•
Menger’s Theorem for Disjoint Paths
•
Path Packing
Outline
Vertex Disjoint S-T Paths
Set of S-T Paths with no common vertex
v
8
v
0
v
1
v
2
v
3
v
4
v
5
v
6
v
9
v
7
T
S
Vertex Disjoint S-T Paths
Set of S-T Paths with no common vertex
v
8
v
0
v
1
v
2
v
3
v
4
v
5
v
6
v
9
v
7
✓
T
S
Vertex Disjoint S-T Paths
Set of S-T Paths with no common vertex
v
8
v
0
v
1
v
2
v
3
v
4
v
5
v
6
v
9
v
7
✗
Common
Vertex
v
7
T
S
Vertex Disjoint S-T Paths
Set of S-T Paths with no common vertex
v
8
v
0
v
1
v
2
v
3
v
4
v
5
v
6
v
9
v
7
✗
Common
Vertex
v
0
T
S
Internally Vertex Disjoint s-t Paths
Set of s-t Paths with no common internal vertex
v
8
v
0
v
1
v
2
v
3
v
4
v
5
v
6
v
9
v
7
t
s
Internally Vertex Disjoint s-t Paths
Set of s-t Paths with no common internal vertex
v
8
v
0
v
1
v
2
v
3
v
4
v
5
v
6
v
9
v
7
t
s
✓
Internally Vertex Disjoint s-t Paths
Set of s-t Paths with no common internal vertex
v
8
v
0
v
1
v
2
v
3
v
4
v
5
v
6
v
9
v
7
t
s
✗
Common
Vertex
v
5
Arc Disjoint s-t Paths
Set of s-t Paths with no common arcs
v
8
v
0
v
1
v
2
v
3
v
4
v
5
v
6
v
9
v
7
t
s
Arc Disjoint s-t Paths
Set of s-t Paths with no common arcs
v
8
v
0
v
1
v
2
v
3
v
4
v
5
v
6
v
9
v
7
t
s
✓
Arc Disjoint s-t Paths
Set of s-t Paths with no common arcs
v
8
v
0
v
1
v
2
v
3
v
4
v
5
v
6
v
9
v
7
t
s
✓
•
Preliminaries
•
Menger’s Theorem for Disjoint Paths
–
Vertex Disjoint S-T Paths
–
Internally Vertex Disjoint s-t Paths
–
Arc Disjoint s-t Paths
•
Path Packing
Outline
Set of S-T Paths with no common vertex
v
8
v
0
v
1
v
2
v
3
v
4
v
5
v
6
v
9
v
7
T
S
Vertex Disjoint S-T Paths
Maximum number of
disjoint paths?
Minimum size of
S-T disconnecting
vertex set !!
S-T Disconnecting Vertex Set
Subset U of V which intersects with all S-T Paths
v
8
v
0
v
1
v
2
v
3
v
4
v
5
v
6
v
9
v
7
T
S
✗
S-T Disconnecting Vertex Set
v
8
v
0
v
1
v
2
v
3
v
4
v
5
v
6
v
9
v
7
T
S
✗
Subset U of V which intersects with all S-T Paths
S-T Disconnecting Vertex Set
v
8
v
0
v
1
v
2
v
3
v
4
v
5
v
6
v
9
v
7
T
S
✓
Subset U of V which intersects with all S-T Paths
S-T Disconnecting Vertex Set
v
8
v
0
v
1
v
2
v
3
v
4
v
5
v
6
v
9
v
7
T
S
✓
Subset U of V which intersects with all S-T Paths
Connection
v
8
v
0
v
1
v
2
v
3
v
4
v
5
v
6
v
9
v
7
T
S
Maximum number of
disjoint paths
Minimum size of
S-T disconnecting
vertex set !!
≤
Menger’s Theorem
v
8
v
0
v
1
v
2
v
3
v
4
v
5
v
6
v
9
v
7
T
S
Maximum number of
disjoint paths
Minimum size of
S-T disconnecting
vertex set !!
=
Proof ?
Mathematical Induction on |A|
Menger’s Theorem
v
8
v
0
v
1
v
2
v
3
v
4
v
5
v
6
v
9
v
7
T
S
True for |A| = 0
Assume it is
true for |A| < m
Mathematical Induction on |A|
To be continued
…
(Try working out the rest)
Explore the foundations of discrete optimization in MA2827 with a focus on graph theory, complexity basics, shortest path algorithms, minimum spanning trees, maximum flow, and more. Dive into concepts such as Menger's Theorem, disjoint paths, path packing, and directed graphs. Gain insights into vertex indegree and outdegree, s-t paths, and maximizing flow/minimizing cuts.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Discrete Optimization MA2827 Fondements de l optimisation discr te https://project.inria.fr/2015ma2827/ Slides courtesy of M. Pawan Kumar
Recap of previous lectures Lecture 1 Graph preliminaries Complexity basics Shortest path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall) Lecture 2 Chow-Liu tree Minimum spanning tree (Prim s, Kruskal s) Maximum flow (Ford-Fulkerson, Dinits)
Outline Preliminaries Menger s Theorem for Disjoint Paths Path Packing
Find the max flow/min cut. Show the steps.
Outline Preliminaries Menger s Theorem for Disjoint Paths Path Packing
Directed Graphs (Digraphs) D = (V, A) v0 v1 v4 v2 v5 v3 v6 n vertices or nodes V m arcs A: ordered pairs from V
Indegree of a Vertex D = (V, A) v0 v1 v4 v2 v5 v3 v6 Number of arcs entering the vertex. indeg(v0) = 1, indeg(v1) = 1, indeg(v4) = 2,
Indegree of a Subset of Vertices D = (V, A) v0 v1 v4 v2 v5 v3 v6 Number of arcs entering the subset. indeg({v0,v1}) = 1, indeg({v1,v4}) = 3,
Outdegree of a Vertex D = (V, A) v0 v1 v4 v2 v5 v3 v6 Number of arcs leaving the vertex. outdeg(v0) = 1, outdeg(v1) = 1, outdeg(v2) = 2,
Outdegree of a Subset of Vertices D = (V, A) v0 v1 v4 v2 v5 v3 v6 Number of arcs leaving the subset. outdeg({v0,v1}) = 1, outdeg({v1,v4}) = 2,
s-t Path D = (V, A) v0 v1 v4 v2 v5 v3 v6 Sequence P = (s=v0,a1,v1, ,ak,t=vk), ai = (vi-1,vi) Vertices s=v0,v1, ,t=vk are distinct
S-T Path S D = (V, A) v0 T v1 v4 v2 v5 v3 v6 S and T are subsets of V Any st-path where s S and t T
S-T Path S D = (V, A) v0 T v1 v4 v2 v5 v3 v6 S and T are subsets of V Any st-path where s S and t T
Outline Preliminaries Menger s Theorem for Disjoint Paths Path Packing
Vertex Disjoint S-T Paths S v0 v8 v1 v2 v3 v4 v5 v6 T v7 v9 Set of S-T Paths with no common vertex
Vertex Disjoint S-T Paths S v0 v8 v1 v2 v3 v4 v5 v6 T v7 v9 Set of S-T Paths with no common vertex
Vertex Disjoint S-T Paths S v0 v8 Common Vertex v7 v1 v2 v3 v4 v5 v6 T v7 v9 Set of S-T Paths with no common vertex
Vertex Disjoint S-T Paths S v0 v8 Common Vertex v0 v1 v2 v3 v4 v5 v6 T v7 v9 Set of S-T Paths with no common vertex
Internally Vertex Disjoint s-t Paths s v0 v8 v1 v2 v3 v4 v5 v6 t v7 v9 Set of s-t Paths with no common internal vertex
Internally Vertex Disjoint s-t Paths s v0 v8 v1 v2 v3 v4 v5 v6 t v7 v9 Set of s-t Paths with no common internal vertex
Internally Vertex Disjoint s-t Paths s v0 v8 Common Vertex v5 v1 v2 v3 v4 v5 v6 t v7 v9 Set of s-t Paths with no common internal vertex
Arc Disjoint s-t Paths s v0 v8 v1 v2 v3 v4 v5 v6 t v7 v9 Set of s-t Paths with no common arcs
Arc Disjoint s-t Paths s v0 v8 v1 v2 v3 v4 v5 v6 t v7 v9 Set of s-t Paths with no common arcs
Arc Disjoint s-t Paths s v0 v8 v1 v2 v3 v4 v5 v6 t v7 v9 Set of s-t Paths with no common arcs
Outline Preliminaries Menger s Theorem for Disjoint Paths Vertex Disjoint S-T Paths Internally Vertex Disjoint s-t Paths Arc Disjoint s-t Paths Path Packing
Vertex Disjoint S-T Paths S v0 v8 Maximum number of disjoint paths? v1 v2 v3 Minimum size of S-T disconnecting vertex set !! v4 v5 v6 T v7 v9 Set of S-T Paths with no common vertex
S-T Disconnecting Vertex Set S v0 v8 v1 v2 v3 v4 v5 v6 T v7 v9 Subset U of V which intersects with all S-T Paths
S-T Disconnecting Vertex Set S v0 v8 v1 v2 v3 v4 v5 v6 T v7 v9 Subset U of V which intersects with all S-T Paths
S-T Disconnecting Vertex Set S v0 v8 v1 v2 v3 v4 v5 v6 T v7 v9 Subset U of V which intersects with all S-T Paths
S-T Disconnecting Vertex Set S v0 v8 v1 v2 v3 v4 v5 v6 T v7 v9 Subset U of V which intersects with all S-T Paths
Connection S v0 v8 Maximum number of disjoint paths v1 v2 v3 Minimum size of S-T disconnecting vertex set !! v4 v5 v6 T v7 v9
Mengers Theorem S v0 v8 Maximum number of disjoint paths v1 v2 v3 = Minimum size of S-T disconnecting vertex set !! v4 v5 v6 T Proof ? v7 v9 Mathematical Induction on |A|
Mengers Theorem S v0 v8 True for |A| = 0 v1 v2 v3 Assume it is true for |A| < m v4 v5 v6 To be continued (Try working out the rest) T v7 v9 Mathematical Induction on |A|
