Discrete Optimization: Fundamentals and Applications
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|
