Graph Theory Unit 15 ReviewGraph Theory in Computer Science & Networks

Fundamentals of Graph Theory

• Graphs model relationships between objects represented as vertices (nodes) connected by edges (links)
• Edges can be undirected (bidirectional) or directed (one-way) depending on the relationship between vertices
• Graphs can be weighted, assigning values to edges, or unweighted, treating all edges equally
  • Weighted graphs (road networks with distance) convey additional information about the relationships between vertices
• The degree of a vertex is the number of edges incident to it, with in-degree and out-degree for directed graphs
• Paths are sequences of vertices connected by edges, while cycles are paths that start and end at the same vertex
  • Acyclic graphs contain no cycles (trees)
• Connected graphs have a path between every pair of vertices, while disconnected graphs have isolated components
• Bipartite graphs divide vertices into two disjoint sets, with edges only between sets (modeling relationships like students and courses)

Graph Representations and Types

• Adjacency matrix represents a graph using a square matrix, with entries indicating the presence or weight of edges between vertices
  • 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 linked lists, with each list containing the neighbors of a vertex
  • Space complexity of $O(V+E)$, efficient for sparse graphs
  • Allows for faster traversal of a vertex's neighbors compared to the adjacency matrix
• Edge list is a simple representation storing a list of edges, each defined by its endpoints and optional weight
• Directed graphs (digraphs) have edges with a specific direction, modeling one-way relationships (web page links)
• Undirected graphs treat edges as bidirectional, suitable for symmetric relationships (friendship networks)
• Weighted graphs assign values to edges, quantifying the strength or cost of connections (road distances, link bandwidths)
• Bipartite graphs have two disjoint vertex sets, with applications in matching problems (job assignments)
• Trees are connected acyclic graphs, modeling hierarchical structures (file systems, organization charts)

Graph Traversal Algorithms

• Breadth-First Search (BFS) explores a graph level by level, visiting all neighbors of a vertex before moving to the next level
  • Implemented using a queue data structure, ensuring vertices are visited in order of their distance from the starting vertex
  • Time complexity of $O(V+E)$, suitable for finding shortest paths in unweighted graphs
• Depth-First Search (DFS) explores a graph by following a path as far as possible before backtracking
  • Implemented using a stack data structure, allowing for the exploration of a vertex's descendants before its siblings
  • Time complexity of $O(V+E)$, useful for detecting cycles and exploring connected components
• Both BFS and DFS can be used to determine graph connectivity and generate spanning trees
• Topological sorting orders the vertices of a directed acyclic graph (DAG) such that for every directed edge $(u, v)$, vertex $u$ comes before $v$
  • Implemented using DFS and tracking the order in which vertices are visited
  • Applications in scheduling tasks with dependencies and course prerequisites
• Connected components can be identified using graph traversal algorithms, with BFS or DFS starting from each unvisited vertex

Shortest Path Problems

• Shortest path problems aim to find the path with the minimum total weight between two vertices in a weighted graph
• Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices
  • Maintains a priority queue of vertices, prioritizing the vertex with the smallest tentative distance
  • Time complexity of $O((V+E) \log V)$ using a binary heap, or $O(V^2)$ with an array
• Bellman-Ford algorithm handles graphs with negative edge weights and detects negative cycles
  • Relaxes all edges $V-1$ times, updating the shortest path estimates
  • Time complexity of $O(VE)$, slower than Dijkstra's but more versatile
• Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices in a weighted graph
  • Uses dynamic programming to iteratively improve the shortest path estimates
  • Time complexity of $O(V^3)$, suitable for dense graphs
• A* search is an informed shortest path algorithm that uses heuristics to guide the search towards the target vertex
  • Combines the actual distance from the source with an estimated distance to the target
  • Efficiently finds shortest paths in large graphs with good heuristics (navigation systems)

Minimum Spanning Trees

• A minimum spanning tree (MST) is a subgraph that connects all vertices with the minimum total edge weight
• Kruskal's algorithm builds the MST by greedily adding the edges with the smallest weight, avoiding cycles
  • Uses a disjoint set data structure to efficiently check for cycles
  • Time complexity of $O(E \log E)$ or $O(E \log V)$ with a union-find data structure
• Prim's algorithm grows the MST from a single vertex, adding the nearest unvisited vertex at each step
  • Maintains a priority queue of vertices, prioritizing the vertex with the smallest edge weight to the MST
  • Time complexity of $O((V+E) \log V)$ using a binary heap, or $O(V^2)$ with an array
• Both Kruskal's and Prim's algorithms produce the same MST, but their efficiency depends on the graph density and representation
• MSTs have applications in network design (minimizing the cost of connecting nodes) and clustering (single-linkage clustering)
• The cut property states that the lightest edge crossing any cut must be part of the MST, ensuring the correctness of greedy algorithms

Network Flow and Matching

• Network flow problems model the maximum flow of a commodity through a network, with applications in transportation and resource allocation
• The maximum flow problem aims to find the largest possible flow from a source vertex to a sink vertex, subject to edge capacities
• Ford-Fulkerson algorithm iteratively finds augmenting paths from source to sink, updating the flow along the path
  • Time complexity depends on the choice of augmenting paths, with $O(E \max \\{flow\\})$ for integer capacities
• Edmonds-Karp algorithm is an implementation of Ford-Fulkerson that uses BFS to find the shortest augmenting path
  • Guarantees a time complexity of $O(VE^2)$, improving upon the general Ford-Fulkerson algorithm
• Dinic's algorithm further improves the time complexity to $O(V^2E)$ by using level graphs and blocking flows
• The max-flow min-cut theorem states that the maximum flow in a network equals the minimum capacity of a cut separating the source and sink
• Bipartite matching problems can be solved using network flow algorithms by constructing a flow network with appropriate capacities
  • Maximum bipartite matching finds the largest possible matching in a bipartite graph (job assignments, college admissions)
  • Minimum vertex cover identifies the smallest set of vertices that covers all edges in a bipartite graph (facility location)

Graph Coloring and Independence

• Graph coloring assigns colors to vertices such that no two adjacent vertices have the same color
• The chromatic number of a graph is the minimum number of colors needed for a proper coloring
  • Determining the chromatic number is NP-hard for general graphs
• Greedy coloring algorithms (Welsh-Powell, largest-degree-first) provide upper bounds on the chromatic number
  • Iteratively color vertices in a specific order, assigning the smallest available color
• Graph coloring has applications in scheduling (exam timetabling, frequency assignment) and register allocation in compilers
• An independent set is a subset of vertices with no edges between them, while a clique is a complete subgraph
  • The maximum independent set and maximum clique problems are NP-hard for general graphs
• The independence number of a graph is the size of the largest independent set
• The clique number of a graph is the size of the largest clique
• The relationship between the independence number $\\alpha(G)$ and the clique number $\\omega(G)$ is $\\alpha(G) \\omega(\\bar{G}) \\leq |V|$, where $\\bar{G}$ is the complement of $G$

Applications in Computer Networks

• Graphs model the topology and connectivity of computer networks, with vertices representing devices and edges representing links
• Shortest path algorithms (Dijkstra's, Bellman-Ford) are used in routing protocols (OSPF, BGP) to find optimal paths for data transmission
  • Routing tables store the shortest paths to various network destinations
• Minimum spanning trees (Kruskal's, Prim's) are used in network design to minimize the cost of connecting devices
  • Spanning tree protocols (STP, RSTP) prevent loops in switched Ethernet networks
• Network flow algorithms (Ford-Fulkerson, Edmonds-Karp) optimize the allocation of bandwidth and resources in networks
  • Traffic engineering and congestion control rely on maximum flow and minimum cut computations
• Graph coloring is applied in channel assignment problems, ensuring efficient use of frequency spectrum in wireless networks
• Bipartite matching algorithms (Hungarian algorithm) are used in content delivery networks (CDNs) to assign users to servers
• Centrality measures (degree, betweenness, closeness) identify critical nodes in networks for reliability and security analysis
  • Degree centrality quantifies the number of connections a node has
  • Betweenness centrality measures the extent to which a node lies on the shortest paths between other nodes
  • Closeness centrality assesses how close a node is to all other nodes in the network
• Community detection algorithms (Girvan-Newman, Louvain) identify closely connected groups of nodes in social and communication networks