graph-theory-math

# Graph Theory ## What I do I provide comprehensive expertise in graph theory, the mathematical study of networks consisting of vertices connected by edges. I enable you to analyze graph properties, implement traversal algorithms, solve shortest path problems, compute network flows, find matchings, detect communities, and solve graph coloring problems. My knowledge spans from fundamental graph properties to advanced algorithms essential for social network analysis, transportation systems, computer networks, and optimization problems. ## When to use me Use graph theory when you need to: find shortest paths in routing and navigation, solve network flow problems for resource allocation, detect communities in social networks, find maximum matchings in assignment problems, analyze connectivity and reliability of networks, schedule tasks with dependencies, solve puzzles like Sudoku as graph coloring, analyze social network influence, or optimize supply chain and logistics. ## Core Concepts - **Graph Representations**: Adjacency matrices and lists for storing graphs with different space/time tradeoffs. - **Graph Traversal**: BFS and DFS algorithms for systematic exploration of graph vertices. - **Shortest Path Algorithms**: Dijkstra's, Bellman-Ford, and Floyd-Warshall for finding optimal paths. - **Network Flow**: Max-flow min-cut theorem and Ford-Fulkerson for flow optimization. - **Matching**: Pairing vertices without sharing edges for assignment and pairing problems. - **Connectivity**: Properties of connected components and techniques for finding them. - **Graph Coloring**: Assigning colors to vertices so adjacent vertices have different colors. - **Eulerian and Hamiltonian Paths**: Traversing all edges or vertices exactly once. - **Centrality Measures**: Degree, betweenness, and closeness for identifying important vertices. - **Community Detection**: Clustering algorithms for finding densely connected subgroups. ## Code Examples ### Graph Representations and Traversal ```python from collections import deque import heapq class Graph: def __init__(self, directed=False): self.adjacency = {} self.directed = directed def add_vertex(self, v): if v not in self.adjacency: self.adjacency[v] = [] def add_edge(self, u, v, weight=1): self.add_vertex(u) self.add_vertex(v) self.adjacency[u].append((v, weight)) if not self.directed: self.adjacency[v].append((u, weight)) def bfs(self, start): """Breadth-first search.""" visited = {start} queue = deque([start]) order = [] while queue: vertex = queue.popleft() order.append(vertex) for neighbor, _ in self.adjacency[vertex]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return order def dfs_iterative(self, start): """Depth-first search (iterative).""" visited = set() stack = [start] order = [] while stack: vertex = stack.pop() if vertex not in visited: visited.add(vertex) order.append(vertex) for neighbor, _ in self.adjacency[vertex]: if neighbor not in visited: stack.append(neighbor) return order def dfs_recursive(self, start): """Depth-first search (recursive).""" visited = set() order = [] def dfs(v): visited.add(v) order.append(v) for neighbor, _ in self.adjacency[v]: if neighbor not in visited: dfs(neighbor) dfs(start) return order # Build example graph g = Graph() edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 4), (3, 4), (4, 5)] for u, v in edges: g.add_edge(u, v) print(f"BFS from 0: {g.bfs(0)}") print(f"DFS from 0: {g.dfs_iterative(0)}") # Connected components def connected_components(graph): """Find all connected components.""" visited = set() components = [] for vertex in graph.adjacency: if vertex not in visited: component = set(graph.bfs(vertex)) visited.update(component) components.append(component) return components components = connected_components(g) print(f"Connected components: {components}") # Check bipartiteness def is_bipartite(graph): """Check if graph is bipartite using BFS.""" color = {} for start in graph.adjacency: if start in color: continue color[start] = 0 queue = deque([start]) while queue: v = queue.popleft() for neighbor, _ in graph.adjacency[v]: if neighbor not in color: color[neighbor] = 1 - color[v] queue.append(neighbor) elif color[neighbor] == color[v]: return False return True print(f"Is bipartite: {is_bipartite(g)}") ``` ### Shortest Path Algorithms ```python import heapq import math def dijkstra(graph, start, end=None): """Dijkstra's shortest path algorithm.""" distances = {v: float('inf') for v in graph.adjacency} distances[start] = 0 predecessors = {start: None} pq = [(0, start)] visited = set() while pq: dist, vertex = heapq.heappop(pq) if vertex in visited: continue visited.add(vertex) if vertex == end: break for neighbor, weight in graph.adjacency[vertex]: if neighbor in visited: continue new_dist = dist + weight if new_dist < distances[neighbor]: distances[neighbor] = new_dist predecessors[neighbor] = vertex heapq.heappush(pq, (new_dist, neighbor)) return distances, predecessors def bellman_ford(graph, start): """Bellman-Ford algorithm for graphs with negative weights.""" distances = {v: float('inf') for v in graph.adjacency} distances[start] = 0 predecessors = {} n = len(graph.adjacency) for _ in range(n - 1): for u in graph.adjacency: for v, w in graph.adjacency[u]: if distances[u] != float('inf') and distances[u] + w < distances[v]: distances[v] = distances[u] + w predecessors[v] = u # Check for negative cycles for u in graph.adjacency: for v, w in graph.adjacency[u]: if distances[u] != float('inf') and distances[u] + w < distances[v]: return None, None # Negative cycle detected return distances, predecessors def floyd_warshall(graph): """Floyd-Warshall for all-pairs shortest paths.""" n = len(graph.adjacency) vertices = list(graph.adjacency.keys()) idx = {v: i for i, v in enumerate(vertices)} # Initialize distance matrix dist = [[float('inf')] * n for _ in range(n)] for i in range(n): dist[i][i] = 0 for u in graph.adjacency: for v, w in graph.adjacency[u]: i, j = idx[u], idx[v] dist[i][j] = min(dist[i][j], w) # Floyd-Warshall for k in range(n): for i in range(n): for j in range(n): if dist[i][k] + dist[j][k] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] return dist, vertices # Example with weighted graph gw = Graph() weighted_edges = [(0, 1, 4), (0, 2, 2), (1, 2, 1), (1, 3, 5), (2, 4, 10), (3, 4, 2)] for u, v, w in weighted_edges: gw.add_edge(u, v, w) distances, predecessors = dijkstra(gw, 0) print(f"Dijkstra from 0: distances = {distances}") # Reconstruct path def reconstruct_path(predecessors, start, end): path = [] current = end while current is not None: path.append(current) current = predecessors.get(current) return list(reversed(path)) path = reconstruct_path(predecessors, 0, 4) print(f"Shortest path from 0 to 4: {path}") # Negative weight example gn = Graph() gn.add_edge(0, 1, 4) gn.add_edge(0, 2, 2) gn.add_edge(1, 2, -3) gn.add_edge(2, 3, 2) gn.add_edge(1, 3, 3) gn.add_edge(3, 1, -1) dist_neg, pred_neg = bellman_ford(gn, 0) if dist_neg is None: print("Negative cycle detected!") else: print(f"Bellman-Ford: {dist_neg}") ``` ### Network Flow ```python import copy class FlowNetwork: def __init__(self): self.graph = {} self.capacity = {} self.flow = {} def add_edge(self, u, v, capacity): if u not in self.graph: self.graph[u] = [] if v not in self.graph: self.graph[v] = [] self.graph[u].append(v) self.graph[v].append(u) # Residual edge self.capacity[(u, v)] = capacity self.capacity[(v, u)] = 0 self.flow[(u, v)] = 0 self.flow[(v, u)] = 0 def bfs_level_graph(self, source, sink): """BFS to build level graph.""" level = {source: 0} queue = [source] while queue: u = queue.pop(0) for v in self.graph[u]: if v not in level and self.capacity[(u, v)] - self.flow[(u, v)] > 0: level[v] = level[u] + 1 queue.append(v) return level def dfs_blocking_flow(self, u, sink, flow, level, current_flow): """DFS to find blocking flow.""" if u == sink: return flow for i in range(current_flow[u], len(self.graph[u])): v = self.graph[u][i] if v in level and self.capacity[(u, v)] - self.flow[(u, v)] > 0: min_cap = min(flow, self.capacity[(u, v)] - self.flow[(u, v)]) pushed = self.dfs_blocking_flow(v, sink, min_cap, level, current_flow) if pushed > 0: self.flow[(u, v)] += pushed self.flow[(v, u)] -= pushed return pushed current_flow[u] += 1 return 0 def max_flow(self, source, sink): """Dinic's algorithm for max flow.""" max_flow = 0 while True: level = self.bfs_level_graph(source, sink) if sink not in level: break current_flow = {u: 0 for u in self.graph} while True: pushed = self.dfs_blocking_flow(source, sink, float('inf'), level, current_flow) if pushed == 0: break max_flow += pushed return max_flow # Example: Maximum flow in network flow_net = FlowNetwork() # Add edges with capacities flow_net.add_edge('S', 'A', 10) flow_net.add_edge('S', 'B', 5) flow_net.add_edge('A', 'B', 15) flow_net.add_edge('A', 'T', 10) flow_net.add_edge('B', 'T', 10) max_flow = flow_net.max_flow('S', 'T') print(f"Maximum flow: {max_flow}") # Minimum cut def min_cut(flow_net, source): """Find minimum cut using residual graph.""" visited = {source} queue = [source] while queue: u = queue.pop(0) for v in flow_net.graph[u]: if v not in visited and flow_net.capacity[(u, v)] - flow_net.flow[(u, v)] > 0: visited.add(v) queue.append(v) return visited cut = min_cut(flow_net, 'S') print(f"Min cut (reachable from S): {cut}") ``` ### Graph Coloring and Matching ```python import itertools def greedy_coloring(graph): """Graph coloring using greedy algorithm.""" colors = {} available_colors = {} for v in graph.adjacency: available_colors[v] = set() for v in graph.adjacency: # Find colors used by neighbors used_colors = {colors.get(n) for n in graph.adjacency[v] if n in colors} # Find smallest available color color = 0 while color in used_colors: color += 1 colors[v] = color return colors def graph_coloring_backtracking(graph, colors, current_assignment=None): """Backtracking graph coloring (exact algorithm).""" if current_assignment is None: current_assignment = {} # Check if all vertices colored if len(current_assignment) == len(graph.adjacency): return current_assignment # Select uncolored vertex with most constraints uncolored = [v for v in graph.adjacency if v not in current_assignment] vertex = min(uncolored, key=lambda v: sum(1 for n in graph.adjacency[v] if n in current_assignment)) # Try each color used_colors = {current_assignment.get(n) for n in graph.adjacency[vertex] if n in current_assignment} for color in range(colors): if color not in used_colors: current_assignment[vertex] = color result = graph_coloring_backtracking(graph, colors, current_assignment) if result is not None: return result del current_assignment[vertex] return None # Graph coloring example gc = Graph() gc.add_edge(0, 1)