Discrete Optimization: Graph Theory Fundamentals

discrete optimization lecture 1 l.w
1 / 208
Embed
Share

"Explore the basics of graph theory in discrete optimization through topics such as undirected graphs, neighboring vertices, parallel edges, loops, and more. Understand key concepts like walks, paths, and vertex degrees in simple graphs."

  • Optimization
  • Graph Theory
  • Discrete
  • Paths
  • Algorithms
rayaanacharya
kai_kul Follow

Uploaded on | 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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

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

E N D

Presentation Transcript

  1. Discrete Optimization Lecture 1 Shortest paths Slides courtesy of M. Pawan Kumar Slides available online https://project.inria.fr/2015ma2827/

  2. Outline Graph Preliminaries Undirected Graphs Directed Graphs Complexity Preliminaries Shortest Path Algorithms

  3. Undirected Graphs G = (V, E) v0 v1 v4 v2 v5 v3 v6 n vertices or nodes V m edges E: unordered pairs from V

  4. Neighboring or Adjacent Vertices G = (V, E) v0 v1 v4 v2 v5 v3 v6 Connected by an edge e = (u,v) = (v,u). v0 and v1 adjacent, v0 and v5 not adjacent,

  5. Parallel Edges G = (V, E) v0 v1 v4 v2 v5 v3 v6 Represented by the same pair of vertices.

  6. Loops G = (V, E) v0 v1 v4 v2 v5 v3 v6 Edges that connect a vertex to itself.

  7. Simple Graphs G = (V, E) v0 v1 v4 v2 v5 v3 v6 Graphs without parallel edges and without loops.

  8. Degree of a Vertex G = (V, E) v0 v1 v4 v2 v5 v3 v6 Number of edges incident on the vertex. deg(v0) = 2, deg(v1) = 2, deg(v4) = 3,

  9. Walk G = (V, E) v0 v1 v4 v2 v5 v3 v6 Sequence P = (v0,e1,v1, ,ek,vk), ei = (vi-1,vi) v0, (v0,v4), v4, (v4,v2), v2, (v2,v5), v5, (v5,v4), v4

  10. Path G = (V, E) v0 v1 v4 v2 v5 v3 v6 Sequence P = (v0,e1,v1, ,ek,vk), ei = (vi-1,vi) Vertices v0,v1, ,vk are distinct

  11. Length of a Walk G = (V, E) v0 v1 v4 v2 v5 v3 v6 Number of edges: k Length of above walk = 5

  12. Length of a Walk G = (V, E) v0 4 2 v1 v4 l: E R 2 1 1 5 v2 v5 1 -2 v3 v6 4 Sum of lengths of all edges: i l(ei) Length of above walk = 4+2+5-2+4 = 13

  13. Closed Walk G = (V, E) v0 v1 v4 v2 v5 v3 v6 Sequence P = (v0,e1,v1, ,ek,vk), ei = (vi-1,vi) v0 = vk

  14. Circuit G = (V, E) v0 v1 v4 v2 v5 v3 v6 Sequence P = (v0,e1,v1, ,ek,vk), ei = (vi-1,vi) v0 = vk Vertices v0,v1, ,vk-1 are distinct

  15. Outline Graph Preliminaries Undirected Graphs Directed Graphs Complexity Preliminaries Shortest Path Algorithms

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

  17. Neighboring or Adjacent Vertices D = (V, A) v0 v1 v4 v2 v5 v3 v6 Connected by an arc a = (u,v). v0 is the inneighbor of v4

  18. Neighboring or Adjacent Vertices D = (V, A) v0 v1 v4 v2 v5 v3 v6 Connected by an arc a = (u,v). v4 is the outneighbor of v0

  19. Parallel Arcs D = (V, A) v0 v1 v4 v2 v5 v3 v6 Represented by the same ordered pair of vertices.

  20. Loops D = (V, A) v0 v1 v4 v2 v5 v3 v6 Arcs that connect a vertex to itself.

  21. Simple Graphs D = (V, A) v0 v1 v4 v2 v5 v3 v6 Graphs without parallel arcs and without loops.

  22. Underlying Undirected Graph D = (V, A) v0 v1 v4 v2 v5 v3 v6 Graphs obtained by ignoring orientation of arcs.

  23. Underlying Undirected Graph G = (V, E) v0 v1 v4 v2 v5 v3 v6 Graphs obtained by ignoring orientation of arcs.

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

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

  26. Walk D = (V, A) v0 v1 v4 v2 v5 v3 v6 Sequence P = (v0,a1,v1, ,ak,vk), ai = (vi-1,vi) v0, (v0,v4), v4, (v4,v5), v5, (v5,v2), v2, (v2,v4), v4

  27. Path D = (V, A) v0 v1 v4 v2 v5 v3 v6 Sequence P = (v0,a1,v1, ,ak,vk), ai = (vi-1,vi) Vertices v0,v1, ,vk are distinct

  28. Length of a Walk D = (V, A) v0 v1 v4 v2 v5 v3 v6 Number of arcs: k Length of above walk = 4

  29. Length of a Walk D = (V, A) v0 4 2 v1 v4 l: E R 2 1 1 5 v2 v5 1 -2 v3 v6 4 Sum of lengths of all edges: i l(ei) Length of above walk = 4+1+5+1 = 11

  30. Closed Walk D = (V, A) v0 v1 v4 v2 v5 v3 v6 Sequence P = (v0,a1,v1, ,ak,vk), ai = (vi-1,vi) v0 = vk

  31. Circuit D = (V, A) v0 v1 v4 v2 v5 v3 v6 Sequence P = (v0,a1,v1, ,ak,vk), ai = (vi-1,vi) v0 = vk Vertices v0,v1, ,vk-1 are distinct

  32. Outline Graph Preliminaries Complexity Preliminaries Shortest Path Algorithms

  33. f(n) O(g(n)) There exists k > 0 and n0 such that f(n) k g(n) for all n n0 f(n) = 5n2 + 3nlog(n) f(n) = 5n3 + 3nlog(n) g(n) = n2 g(n) = n2

  34. Outline Graph Preliminaries Complexity Preliminaries Shortest Path Algorithms Breadth-first Search Dijkstra s Method Bellman-Ford Method Floyd-Warshall Method

  35. The Shortest Path Problem Find the shortest path from s to t v0 Length of path = Number of arcs v1 v4 v2 v5 v3 v6 v7

  36. The Shortest Path Problem Find the shortest path from s to t v0 3 2 Length of path = Length of arcs -1 v1 v4 3 1 2 6 v2 v5 3 5 -3 2 v3 v6 1 7 v7

  37. Applications Minimize number of stops (lengths = 1) Minimize amount of time (positive lengths)

  38. Applications Convert 1 ounce of gold to US dollars 1 GOLD = 455.2 * 0.6677 * 1.0752 = 327.28 USD Take log to convert products to sums (possibly negative lengths) GBP 1.0 1.4599 189.05 2.1904 1.5714 0.004816 EUR 0.6853 1.0 129.52 1.4978 1.0752 0.003295 JPY 0.005290 0.007721 1.0 0.011574 0.008309 0.000025 5 CHF 0.4569 0.6677 85.4694 1.0 0.7182 0.002201 USD 0.6368 0.9303 120.4 1.3941 1.0 0.003065 GOLD 208.1 304.028 39346.7 455.2 327.25 1.0 GBP EUR JPY CHF USD GOLD Example courtesy of Robert Sedgewick

  39. Outline Graph Preliminaries Complexity Preliminaries Shortest Path Algorithms Breadth-first Search Dijkstra s Method Bellman-Ford Method Floyd-Warshall Method

  40. Breadth-First Search D = (V, A) s v0 Assumption: all lengths = 1 v1 v4 Length of path = Number of arcs v2 v5 |V| = n, |A| = m v3 v6 v7

  41. Breadth-First Search Queue is empty. All nodes unvisited. Push s to queue. Set length(s) = 0. While ( t is unvisited) Pop u from queue. Length(unvisited outneighbors) = Length(u)+1 Push unvisited outneighbors to queue End Shortest path to all vertices from s

  42. Breadth-First Search Populate the queue with s s v0 Length of s = 0. v1 v4 v2 v5 Queue v0 v3 v6 Length v0 0 v1 v2 v3 v4 v5 v6 v7 v7

  43. Breadth-First Search u = v0 Pop from the queue. s v0 Length(unvisited outneighbors) = Length(u) + 1 v1 v4 Push unvisited outneighbors to queue. v2 v5 Queue v1 v4 v3 v6 Length v0 0 v1 1 v2 v3 v4 1 v5 v6 v7 v7

  44. Breadth-First Search u = v1 Pop from the queue. s v0 Length(unvisited outneighbors) = Length(u) + 1 v1 v4 Push unvisited outneighbors to queue. v2 v5 Queue v4 v2 v3 v6 Length v0 0 v1 1 v2 2 v3 v4 1 v5 v6 v7 v7

  45. Breadth-First Search u = v4 Pop from the queue. s v0 Length(unvisited outneighbors) = Length(u) + 1 v1 v4 Push unvisited outneighbors to queue. v2 v5 Queue v2 v5 v3 v6 Length v0 0 v1 1 v2 2 v3 v4 1 v5 2 v6 v7 v7

  46. Breadth-First Search u = v2 Pop from the queue. s v0 Length(unvisited outneighbors) = Length(u) + 1 v1 v4 Push unvisited outneighbors to queue. v2 v5 Queue v5 v3 v3 v6 Length v0 0 v1 1 v2 2 v3 3 v4 1 v5 2 v6 v7 v7

  47. Breadth-First Search u = v5 Pop from the queue. s v0 Length(unvisited outneighbors) = Length(u) + 1 v1 v4 Push unvisited outneighbors to queue. v2 v5 Queue v3 v6 v3 v6 Length v0 0 v1 1 v2 2 v3 3 v4 1 v5 2 v6 3 v7 v7

  48. Breadth-First Search u = v3 Pop from the queue. s v0 Length(unvisited outneighbors) = Length(u) + 1 v1 v4 Push unvisited outneighbors to queue. v2 v5 Queue v6 v3 v6 Length v0 0 v1 1 v2 2 v3 3 v4 1 v5 2 v6 3 v7 4 v7

  49. Breadth-First Search Queue is empty. All nodes unvisited. Push s to queue. Set length(s) = 0. While ( t is unvisited) Pop u from queue. Length(unvisited outneighbors) = Length(u)+1 Push unvisited outneighbors to queue End Shortest path to all vertices from s

  50. Analysis Time Complexity : O( n + m ) Queue operations At most n elements in the queue In the worst case, all arcs will be visited once

Related


No related presentations.

More Related Content