Paths And Cycles

Introduction

Paths and cycles form the backbone of graph theory. They describe routes and loops within networks. Analysis of these structures underpins connectivity, routing, and circuit detection. Applications span computer science, biology, logistics, and more.

"A graph without paths is a mere collection of points; with paths, it becomes a map of potential journeys." -- Reinhard Diestel

Basic Definitions

Graph

Set G = (V, E) where V is vertices, E is edges (unordered pairs in undirected, ordered pairs in directed).

Path

Sequence of edges connecting a sequence of distinct vertices with no repetition of edges.

Cycle

Closed path where first and last vertices are the same, no other repetitions.

Walk

Sequence of vertices where edges exist between consecutive vertices; repetition allowed.

Trail

Walk with no repeated edges but possible vertex repetition.

Types of Paths

Simple Path

Path with no repeated vertices or edges.

Directed Path

Path respects edge directions in a directed graph.

Weighted Path

Edges have weights; path weight is sum of edges' weights.

Shortest Path

Path with minimum total weight or minimum edges between two vertices.

Longest Path

Path with maximum length; problem is NP-hard in general graphs.

Cycles and Circuits

Cycle

Closed simple path; no repeated vertices except start/end.

Circuit

Closed trail allowing repeated vertices but no repeated edges.

Chordless Cycle

Cycle with no chords (edges connecting nonconsecutive vertices).

Directed Cycle

Cycle following edge direction in directed graphs.

Fundamental Cycle

Cycle created by adding an edge to a spanning tree.

Directed and Undirected Graphs

Undirected Paths

Edges unordered; paths symmetric.

Directed Paths

Edges ordered; paths must follow direction.

Strong Connectivity

Every vertex reachable from every other via directed paths.

Weak Connectivity

Connectivity ignoring edge directions.

Acyclic Graphs

Graphs with no directed cycles (DAGs).

Path Properties

Length

Number of edges in the path.

Uniqueness

Conditions for unique paths between vertices.

Connectivity

Existence of paths determines connectedness.

Path Decomposition

Breaking graphs into path sets covering vertices or edges.

Distance

Minimum length of path between vertices.

Cycle Properties

Length

Number of edges in the cycle.

Cycle Basis

Set of cycles forming a basis for cycle space.

Parity

Even or odd length cycles; relevant for bipartite graphs.

Cycle Detection

Algorithms to find cycles efficiently.

Cycle Space

Vector space over cycles under symmetric difference.

Special Paths

Eulerian Path

Path using every edge exactly once.

Hamiltonian Path

Path visiting every vertex exactly once.

Geodesic Path

Shortest path between two vertices.

Induced Path

Path inducing a subgraph with no extra edges.

Monotone Path

Path with vertices increasing or decreasing by label or weight.

Special Cycles

Eulerian Cycle

Cycle using every edge exactly once.

Hamiltonian Cycle

Cycle visiting every vertex exactly once.

Odd and Even Cycles

Parity affects graph properties like bipartiteness.

Chordless Cycle

Cycle with no chords; also called induced cycle.

Face Cycle

Cycle bounding a face in planar graphs.

Algorithms for Paths

Dijkstra’s Algorithm

Finds shortest paths in weighted graphs with nonnegative weights.

Breadth-First Search (BFS)

Shortest path in unweighted graphs.

Depth-First Search (DFS)

Explores graph for path existence and traversal ordering.

Bellman-Ford Algorithm

Shortest paths in graphs with negative weights.

Floyd-Warshall Algorithm

All-pairs shortest paths in weighted graphs.

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

Algorithms for Cycles

Cycle Detection via DFS

Detect back edges to find cycles in directed graphs.

Tarjan’s Algorithm

Finds strongly connected components, implying cycles.

Hierholzer’s Algorithm

Constructs Eulerian trails and cycles.

Backtracking for Hamiltonian Cycles

Exhaustive search for Hamiltonian cycles, NP-complete.

Chordless Cycle Detection

Specialized algorithms for induced cycles.

Applications

Network Routing

Shortest paths optimize data transmission routes.

Biological Networks

Paths represent metabolic or gene regulatory pathways.

Logistics and Transportation

Eulerian and Hamiltonian paths model efficient delivery routes.

Electrical Circuits

Cycles correspond to closed current loops.

Social Network Analysis

Connectivity and cycles reveal community structures.

Example: Eulerian Path Condition in Undirected GraphInput: graph G=(V,E)Condition: - All vertices have even degree, or - Exactly two vertices have odd degreeIf condition holds: Eulerian path existsElse: No Eulerian path

References

• Diestel, R., Graph Theory, Springer, 5th Edition, 2017, pp. 1-400.
• West, D.B., Introduction to Graph Theory, Prentice Hall, 2nd Edition, 2001, pp. 1-600.
• Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., Introduction to Algorithms, MIT Press, 3rd Edition, 2009, pp. 1-1312.
• Tarjan, R.E., Depth-First Search and Linear Graph Algorithms, SIAM Journal on Computing, Vol. 1, 1972, pp. 146-160.
• Hierholzer, C., Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren, Mathematische Annalen, Vol. 6, 1873, pp. 30-32.