Common graph theory problems — [Notes]

· Shortest path problem
· Connectivity —
· Negative Cycles —
· Strongly connected components (SCCs) —
· Traveling salesman problem —
· Finding Bridges —
· Articulation Points —
· Minimum Spanning Tree(MST) —
· Network flow: max flow —

Common Problems -

Shortest path problem

Given a weighted graph, find the shortest path of edges from node A to node B.

• Algorithms — BFS (unweighted graph), Dijkstra’s, Bellman-Ford, Floyd-Warshall, A*, etc.

Source — https://youtu.be/87X57ldq1ok

Connectivity —

• Does there exist a path between node A and node B?
• Algorithms — Use union find data structure or any search algorithm (e.g DFS, BFS).

Source — https://youtu.be/87X57ldq1ok

Negative Cycles —

• Does my weighted digraph have any negative cycles? If so, where?
• → Algorithms — Bellman-Ford and Floyd-Warshall
  Usecase example — currency exchange

Source — https://youtu.be/87X57ldq1ok

Strongly connected components (SCCs) —

• can be thought of as self-contained cycles within a directed graph where every vertex in a given cycle can reach every other vertex in the same cycle.
• → Algorithms — Tarjan’s and Kosaraju’s algorithm

Source — https://youtu.be/87X57ldq1ok

Traveling salesman problem —

• “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?” — Wiki
• → TSP is an NP-hard problem
• → Algorithms: Held-Karp, branch and bound, and many approximation algorithms

Finding Bridges —

• A bridge/cut edge is any edge in a graph whose removal increases the number of connected components.
• → Bridges are important in graph theory because they often hint at weak points, bottlenecks, or vulnerabilities in a graph.
• → Think of the graph as a telephone network, bridges between islands

Articulation Points —

• An articulation point/cut vertex is any node in a graph whose removal increases the number of connected components.
• → Articulation points are important in graph theory because they often hint at weak points, bottlenecks or vulnerabilities in a graph.

Minimum Spanning Tree(MST) —

• A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted graph that connects all the vertices together, without any cycles, and with the minimum
  possible total edge weight/cost. — Wiki
• → It’s a tree (meaning has no cycles) and spans the graph at minimum cost
• → All MSTs of the graph has the same cost and are not necessarily identical.
• → Algorithms — Kruskal’s, Prim’s & Boruvka’s algorithm
• → Application — Designing the least cost network, circuit design, transportation networks, and several approximation algorithms also rely on minimum spanning trees

Network flow: max flow —

• Q: With an infinite input source how much “flow” can we push through the network?
• → Suppose the edges are roads with cars, pipes with water, or hallways with packed with people. Flow represents the volume of water allowed to flow through the pipes, the number of cars the roads can sustain in
  traffic, and the maximum amount of people that can navigate through the hallways.
• → question is important because at some point there is bound to be a bottleneck in our flow graph that limits the amount of stuff we can have traveling on the network making it from point A to point B the maximum flow would then represent things like the volume of water allowed to flow through the network of pipes the number of cars the roads can sustain traffic or the maximum amount of boats allowed on the river with these maximum flow problems. we can identify the bottlenecks that slow down the whole network and fix the edges that have lower capacities.
• → Algorithms: Ford-Fulkerson, Edmonds-Karp, and Dinic’s algorithm