Paths, cycles, and connectivity are key concepts in graph theory. They help us understand how vertices are linked and how information flows through networks. These ideas are crucial for solving real-world problems like finding the quickest route or identifying weak points in a system.

This section builds on earlier graph concepts, introducing more complex structures and algorithms. We'll explore different types of paths and cycles, methods for finding shortest routes, and ways to analyze graph connectivity. These tools are essential for tackling advanced graph problems.

Paths and cycles in graphs

Types of paths and cycles

• A path in a graph is a sequence of vertices connected by edges, where no vertex is repeated
  • The length of a path is the number of edges it contains
• A cycle in a graph is a path that starts and ends at the same vertex, with no repeated edges
  • A simple cycle has no repeated vertices except for the starting/ending vertex (e.g., a-b-c-d-a)
• Eulerian paths and cycles visit every edge exactly once
  • Eulerian paths have distinct starting and ending vertices (e.g., a-b-c-d-e)
  • Eulerian cycles start and end at the same vertex (e.g., a-b-c-d-e-a)
• Hamiltonian paths and cycles visit every vertex exactly once
  • Hamiltonian paths have distinct starting and ending vertices (e.g., a-c-d-b-e)
  • Hamiltonian cycles start and end at the same vertex (e.g., a-c-d-b-e-a)

Shortest paths

• The shortest path between two vertices is a path with the minimum number of edges or the minimum total weight in a weighted graph
• Finding the shortest path is important for applications such as navigation systems, network routing, and optimization problems
• Algorithms for finding shortest paths include Dijkstra's algorithm, Bellman-Ford algorithm, and Floyd-Warshall algorithm

Graph connectivity

Connected and disconnected graphs

• A graph is connected if there exists a path between every pair of vertices
  • In a connected graph, it is possible to reach any vertex from any other vertex by traversing edges
• A graph is disconnected if there exists at least one pair of vertices with no path between them
  • A disconnected graph consists of multiple connected components
• A connected component is a maximal connected subgraph, where there exists a path between any two vertices within the component, but no path exists between vertices in different components
  • The number of connected components in a graph can be determined by performing a depth-first search (DFS) or breadth-first search (BFS)

Cut vertices and bridges

• A cut vertex (or articulation point) is a vertex whose removal increases the number of connected components in the graph
  • Cut vertices are crucial for maintaining the connectivity of a graph (e.g., in a communication network, a cut vertex represents a critical node whose failure can disrupt the network)
• A bridge (or cut edge) is an edge whose removal increases the number of connected components in the graph
  • Bridges are important for identifying critical connections in a graph (e.g., in a road network, a bridge represents a crucial link whose closure can isolate parts of the network)
• The connectivity of a graph is the minimum number of vertices that need to be removed to disconnect the graph or make it trivial (a single vertex)
  • A graph with higher connectivity is more resilient to vertex failures or attacks

Shortest paths in graphs

Dijkstra's algorithm

• Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights
• The algorithm maintains a set of visited vertices and a distance array that stores the shortest distance from the source vertex to each vertex
• At each step, the algorithm selects the unvisited vertex with the smallest distance, marks it as visited, and updates the distances of its neighboring vertices if a shorter path is found
  • The algorithm uses a priority queue (e.g., a min-heap) to efficiently select the vertex with the smallest distance
• The algorithm terminates when all vertices have been visited or the destination vertex is reached
• Dijkstra's algorithm has a time complexity of $O((V+E) \log V)$ using a binary heap, where $V$ is the number of vertices and $E$ is the number of edges

Other shortest path algorithms

• The Bellman-Ford algorithm can handle negative edge weights and detect negative cycles in a graph
  • It has a time complexity of $O(VE)$ and is useful when negative edge weights are present
• The Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices in a weighted graph
  • It has a time complexity of $O(V^3)$ and is based on dynamic programming
• The A search algorithm is an informed search algorithm that uses heuristics to guide the search towards the goal vertex
  • It is widely used in pathfinding and graph traversal problems

Strongly connected components

Strongly connected graphs and components

• A directed graph is strongly connected if there exists a directed path from every vertex to every other vertex
  • In a strongly connected graph, it is possible to reach any vertex from any other vertex by following the directed edges
• A strongly connected component (SCC) is a maximal strongly connected subgraph, where there exists a directed path between any two vertices within the component, but no directed path exists between vertices in different components
  • SCCs represent tightly connected regions in a directed graph
• The condensation of a directed graph is a directed acyclic graph (DAG) formed by contracting each SCC into a single vertex and adding edges between SCCs based on the original graph's edges
  • The condensation graph captures the high-level structure of the directed graph and the relationships between SCCs

Algorithms for finding SCCs

• Tarjan's algorithm finds the SCCs of a directed graph in linear time complexity ($O(V+E)$)
  • It performs a single depth-first search (DFS) and maintains a stack to keep track of visited vertices
  • The algorithm assigns discovery times and low-link values to each vertex to identify SCCs
• Kosaraju's algorithm also finds the SCCs of a directed graph in linear time complexity ($O(V+E)$)
  • It performs two depth-first searches (DFS) on the graph and its transpose (reversing the direction of all edges)
  • The first DFS is used to determine the ordering of vertices, and the second DFS is performed on the transposed graph to identify SCCs
• The number of SCCs in a directed graph can be determined by performing a depth-first search (DFS) on the graph and its transpose
  • Each DFS tree in the second DFS represents an SCC
  • The number of DFS trees in the second DFS equals the number of SCCs in the graph