Discrete Optimization: Fundamentals and Applications

Discrete Optimization
MA2827
Fondements de l’optimisation discrète
https://project.inria.fr/2015ma2827/
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({v
0
,v
1
}) = 1, indeg({v
1
,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({v
0
,v
1
}) = 1, outdeg({v
1
,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)
Slide Note
Embed
Share

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.

  • Discrete Optimization
  • Graph Theory
  • Maximum Flow
  • Mengers Theorem
  • Directed Graphs

Uploaded on Sep 08, 2024 | 0 Views


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


  1. Discrete Optimization MA2827 Fondements de l optimisation discr te https://project.inria.fr/2015ma2827/ Slides courtesy of M. Pawan Kumar

  2. 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)

  3. Outline Preliminaries Menger s Theorem for Disjoint Paths Path Packing

  4. But first

  5. Find the max flow/min cut. Show the steps.

  6. Outline Preliminaries Menger s Theorem for Disjoint Paths Path Packing

  7. 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

  8. 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,

  9. 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,

  10. 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,

  11. 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,

  12. 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

  13. 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

  14. 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

  15. Outline Preliminaries Menger s Theorem for Disjoint Paths Path Packing

  16. 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

  17. 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

  18. 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

  19. 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

  20. 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

  21. 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

  22. 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

  23. 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

  24. 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

  25. 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

  26. 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

  27. 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

  28. 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

  29. 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

  30. 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

  31. 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

  32. 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

  33. 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|

  34. 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|

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#