Undirected Graphs

Definition and Basic Concepts

Undirected Graph Explained

Structure: set of vertices (nodes) and edges (connections). Edge: unordered pair of vertices. Symmetry: edges have no direction; (u,v) = (v,u). Use: models mutual or bidirectional relationships.

Terminology

Vertex (node): fundamental unit. Edge: link connecting vertices. Degree: number of edges incident on a vertex. Loop: edge connecting vertex to itself. Simple graph: no loops or multiple edges.

Mathematical Representation

Graph G = (V, E) where V is vertex set, E is edge set of unordered pairs. |V|=n vertices, |E|=m edges. Undirected edges: {u, v} with u, v ∈ V, u ≠ v for simple graphs.

Graph Representations

Adjacency Matrix

Definition: n×n matrix A for n vertices. A[i][j]=1 if edge exists between i and j, else 0. Symmetric matrix for undirected graphs. Space: O(n²).

Adjacency List

Definition: array or list where each index stores neighbors of vertex. Efficient for sparse graphs. Space: O(n + m). Enables fast iteration over neighbors.

Edge List

Definition: list of edges as pairs (u, v). Simple to build, inefficient for neighbor queries. Space: O(m). Useful for edge-centric algorithms.

Key Properties

Degree of Vertices

Degree: number of edges incident to vertex. Sum of degrees equals twice number of edges: ∑deg(v) = 2m. Even sum property fundamental in graph theory.

Handshaking Lemma

Theorem: sum of all vertex degrees is even. Implication: number of vertices with odd degree is even. Useful for proofs and algorithms.

Simple vs Multigraphs

Simple: no loops, no parallel edges. Multigraph: allows multiple edges between same vertices. Property differences affect algorithm selection.

Traversal Algorithms

Breadth-First Search (BFS)

Mechanism: explores neighbors level-wise using queue. Output: shortest path in unweighted graphs. Complexity: O(n + m).

Depth-First Search (DFS)

Mechanism: explores as deep as possible using stack or recursion. Uses: connectivity, cycle detection, topological ordering in DAGs.

Comparison

BFS: shortest paths, layer information. DFS: path exploration, backtracking. Both linear time in vertices and edges.

function BFS(graph, start): create queue Q mark start as visited enqueue start into Q while Q not empty: vertex = dequeue Q for each neighbor of vertex: if not visited: mark visited enqueue neighbor

Connectivity and Components

Connected Graph

Definition: path exists between every pair of vertices. Important for network reliability and routing.

Connected Components

Subgraphs where vertices are mutually reachable. Algorithm: use DFS/BFS to label components. Number of components: k.

Bridges and Articulation Points

Bridge: edge whose removal increases components. Articulation point: vertex whose removal disconnects graph. Identification via DFS low-link values.

Cycles and Acyclic Graphs

Cycle Definition

Cycle: path starting and ending at same vertex with no repeated edges or vertices except start/end. Presence indicates complexity in graph structure.

Cycle Detection

Method: DFS with parent tracking. Back edge indicates cycle in undirected graphs. Complexity: O(n + m).

Acyclic Graphs

Graphs without cycles. Special case: trees (connected acyclic graphs). Trees have n-1 edges and unique path between any two vertices.

function DFS_Cycle_Detection(graph, vertex, parent): mark vertex visited for each neighbor in graph[vertex]: if not visited: if DFS_Cycle_Detection(graph, neighbor, vertex) == true: return true else if neighbor != parent: return true return false

Pathfinding Techniques

Shortest Path in Unweighted Graphs

Algorithm: BFS provides shortest path length. Tracks predecessors to reconstruct path.

Dijkstra’s Algorithm

Applicable if edges weighted non-negative. Uses priority queue. Complexity: O(m + n log n) with binary heap.

Floyd-Warshall Algorithm

All-pairs shortest paths. Uses dynamic programming. Complexity: O(n³). Suitable for dense graphs.

Applications

Network Modeling

Use: represent computer, social, transportation networks. Undirected edges model bidirectional communication or relationships.

Biological Systems

Model interactions such as protein-protein, ecological networks. Symmetric relationships common in biology.

Scheduling and Resource Allocation

Conflict graphs, resource sharing, task dependencies without directionality. Basis for optimization algorithms.

Algorithmic Complexity

Traversal

DFS/BFS: O(n + m) time, linear in vertices and edges.

Search and Cycle Detection

DFS-based cycle detection also O(n + m). Efficient for large sparse graphs.

Shortest Path

BFS for unweighted: O(n + m). Dijkstra with binary heap: O(m + n log n). Floyd-Warshall: O(n³), impractical for large graphs.

Data Structure Choices

Memory Considerations

Adjacency matrix: high space for large sparse graphs. Adjacency list preferable for scalability.

Performance Trade-offs

Matrix: O(1) edge queries, slow iteration over neighbors. List: O(d) edge queries, fast neighbor traversal.

Implementation Details

Use arrays, linked lists, hash maps depending on language and graph size. Dynamic graphs benefit from adjacency lists.

Advanced Topics

Graph Isomorphism

Determining equivalence between graphs. Computationally challenging; practical heuristics exist.

Planarity and Embeddings

Planar graphs can be drawn without edge crossings. Kuratowski’s theorem defines non-planar subgraphs.

Graph Coloring

Assign colors to vertices so adjacent vertices differ. Applications: scheduling, register allocation.

Common Problems and Solutions

Connectivity Queries

Union-Find data structure supports dynamic connectivity queries efficiently.

Minimum Spanning Tree (MST)

Kruskal’s and Prim’s algorithms find MST in weighted undirected graphs. Essential for network design.

Graph Matching

Finding maximum matching in bipartite or general graphs. Algorithms: Hungarian, Blossom.

References

• West, D. B., Introduction to Graph Theory, Prentice Hall, 2001, pp. 1-500.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C., Introduction to Algorithms, MIT Press, 2009, pp. 631-660.
• Diestel, R., Graph Theory, 5th Edition, Springer, 2017, pp. 1-300.
• Ahuja, R. K., Magnanti, T. L., Orlin, J. B., Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993, pp. 45-120.
• Tarjan, R. E., Depth-First Search and Linear Graph Algorithms, SIAM Journal on Computing, vol. 1, 1972, pp. 146-160.