Combinatorial Optimization Unit 2 review

Graph Theory and Algorithms

2.1

Graph representations

2.2

Graph traversal algorithms

2.3

Shortest path problems

2.4

Minimum spanning trees

2.5

Maximum flow problems

2.6

Matching problems

2.7

Graph coloring

unit 2 review

Graph theory and algorithms form the backbone of many computational problems. This unit covers fundamental concepts like graph representations, traversal methods, and key algorithms for solving common graph-related challenges. Advanced topics include network flow, matching problems, and optimization techniques. Real-world applications span social networks, transportation systems, and biological interactions, showcasing the versatility of graph-based approaches in problem-solving.

Key Concepts and Terminology

Graphs consist of vertices (nodes) connected by edges (links) representing relationships or connections between entities
Directed graphs (digraphs) contain edges with a specific direction, while undirected graphs have edges without a direction
Weighted graphs assign values (weights) to edges, representing costs, distances, or capacities
Degree of a vertex refers to the number of edges incident to it, with in-degree and out-degree for directed graphs
Paths are sequences of vertices connected by edges, with simple paths having no repeated vertices
- Cycles are paths that start and end at the same vertex
- Connected graphs have a path between every pair of vertices
Trees are connected acyclic graphs, while forests are disjoint sets of trees
Bipartite graphs divide vertices into two disjoint sets, with edges only between sets
Planar graphs can be drawn on a plane without edge crossings, while non-planar graphs require edge crossings

Graph Representations and Properties

Adjacency matrix represents a graph using a square matrix, with entries indicating edge presence or weight
- Space complexity of $O(V^2)$ , suitable for dense graphs
- Edge existence and weight lookup in constant time $O(1)$
Adjacency list stores a graph as an array of lists, with each list containing the neighbors of a vertex
- Space complexity of $O(V+E)$ , efficient for sparse graphs
- Allows for efficient traversal of a vertex's neighbors
Edge list is a simple representation storing a list of edges, each represented as a pair of vertices
Incidence matrix represents the relationship between vertices and edges, with rows for vertices and columns for edges
Graph density measures the ratio of actual edges to the maximum possible edges, with sparse and dense graphs
Connectivity properties include connected components, strongly connected components (SCCs) in directed graphs, and bridges/articulation points
Graph isomorphism determines if two graphs are structurally equivalent, with efficient algorithms for special cases

Basic Graph Algorithms

Breadth-First Search (BFS) traverses a graph level by level, exploring all neighbors before moving to the next level
- Finds shortest paths in unweighted graphs and connected components
- Time complexity of $O(V+E)$ using a queue data structure
Depth-First Search (DFS) explores a graph by going as deep as possible before backtracking
- Useful for cycle detection, topological sorting, and finding strongly connected components
- Implemented using a stack or recursion, with time complexity $O(V+E)$
Topological sorting orders the vertices of a directed acyclic graph (DAG) such that for every directed edge $(u,v)$ $(u, v)$ , $u$ $u$ comes before $v$ $v$
- Kahn's algorithm and DFS-based approaches are common
Minimum Spanning Tree (MST) algorithms (Kruskal's, Prim's) find a tree that connects all vertices with minimum total edge weight
- Kruskal's algorithm sorts edges by weight and adds them greedily, avoiding cycles
- Prim's algorithm grows the MST from a starting vertex, adding the cheapest connected edge at each step
Shortest path algorithms (Dijkstra's, Bellman-Ford) find paths with minimum total weight between vertices
- Dijkstra's algorithm uses a priority queue and greedy approach for non-negative weights
- Bellman-Ford handles negative weights and detects negative cycles

Advanced Graph Algorithms

Floyd-Warshall algorithm finds shortest paths between all pairs of vertices using dynamic programming
- Computes a distance matrix in $O(V^3)$ time, handling negative weights but not negative cycles
Johnson's algorithm combines Bellman-Ford and Dijkstra's algorithms for sparse graphs with negative weights
- Reweights edges to eliminate negative weights, then runs Dijkstra's from each vertex
Maximum flow algorithms (Ford-Fulkerson, Edmonds-Karp) find the maximum flow through a network from source to sink
- Ford-Fulkerson uses augmenting paths to increase flow, with Edmonds-Karp using BFS for better performance
Minimum cut algorithms (Karger's, Stoer-Wagner) find a cut with minimum total weight that separates a graph into two parts
Strongly Connected Components (SCCs) algorithms (Kosaraju's, Tarjan's) identify maximal strongly connected subgraphs in directed graphs
- Kosaraju's algorithm uses two DFS passes on the original and transposed graph
- Tarjan's algorithm uses a single DFS with lowlink values and a stack
Bipartite matching algorithms (Hungarian, Hopcroft-Karp) find maximum matchings in bipartite graphs
- Hungarian algorithm solves the assignment problem in $O(V^3)$ time
- Hopcroft-Karp finds maximum matchings in $O(\sqrt{V}E)$ time

Optimization Problems on Graphs

Traveling Salesman Problem (TSP) seeks the shortest tour visiting each vertex exactly once
- NP-hard problem, approximated using heuristics like Christofides' algorithm
Vehicle Routing Problem (VRP) extends TSP with multiple vehicles, capacities, and time windows
- Variants include Capacitated VRP (CVRP), VRP with Time Windows (VRPTW), and VRP with Pickups and Deliveries (VRPPD)
Facility Location Problem aims to optimally place facilities to minimize costs and maximize coverage
- Uncapacitated and capacitated versions, with heuristics and approximation algorithms
Graph Coloring assigns colors to vertices such that no adjacent vertices share the same color
- Chromatic number is the minimum number of colors needed
- Applications in scheduling, register allocation, and frequency assignment
Maximum Independent Set finds the largest subset of vertices with no edges between them
- Complement of the minimum vertex cover problem
Minimum Dominating Set seeks the smallest subset of vertices such that each vertex is either in the set or adjacent to a vertex in the set
- Variants include connected dominating set and independent dominating set

Applications in Real-World Scenarios

Social Networks use graphs to model relationships, with vertices as individuals and edges as connections
- Community detection, influence maximization, and link prediction are common tasks
Transportation Networks represent roads, railways, or flights as edges, with vertices as junctions or stations
- Used for route planning, traffic flow optimization, and logistics
Computer Networks model devices as vertices and connections as edges
- Helps in network design, routing protocols, and resource allocation
Biological Networks depict interactions between biological entities (proteins, genes)
- Protein-protein interaction networks, gene regulatory networks, and metabolic pathways
Recommendation Systems employ bipartite graphs with users and items as vertices, and ratings or interactions as edges
- Collaborative filtering, content-based filtering, and hybrid approaches
Project Scheduling represents tasks as vertices and dependencies as edges
- Critical Path Method (CPM) and Program Evaluation and Review Technique (PERT) for scheduling and resource allocation

Problem-Solving Techniques

Identify the problem type and select an appropriate graph representation
Break down complex problems into subproblems, solving them independently and combining results
Use heuristics and approximation algorithms for NP-hard problems, balancing solution quality and computational efficiency
Employ dynamic programming for problems with overlapping subproblems and optimal substructure
Consider greedy approaches when making locally optimal choices leads to a globally optimal solution
Analyze time and space complexity, optimizing for the given constraints and problem size
Test solutions on small instances, edge cases, and large-scale datasets
Iterate and refine the approach based on feedback and performance analysis