Tree and Cycle Algorithms in Graph Theory
Undirected Graphs and Basic Concepts
- In graph theory, an undirected graph is a set of vertices connected by edges, where the edges have no direction.
- This forms the basis for many important algorithms in computer science and operations research.
Key concepts include:
- Walk: A sequence of vertices and edges, allowing repetition
- Trail: A walk with no repeated edges
- Path: A walk with no repeated vertices
- Circuit: A trail that starts and ends at the same vertex
- Cycle: A path that starts and ends at the same vertex (a simple circuit)
Consider the undirected graph above.
- Walk: A sequence of vertices where consecutive vertices are connected by an edge.
- Example: \( A \to B \to C \to D \to B \to E \)
- Trail: A walk in which no edge is repeated.
- Example: \( A \to B \to C \to D \to E \)
- Path: A trail in which no vertex is repeated.
- Example: \( A \to B \to D \to E \)
- Circuit: A trail that starts and ends at the same vertex.
- Example: \( A \to B \to C \to D \to B \to A \)
- Cycle: A path that starts and ends at the same vertex with no repeated edges or vertices (except the start/end vertex).
- Example: \( A \to B \to C \to D \to A \)
Eulerian Trails and Circuits
- An Eulerian trail is a trail that uses every edge in a graph exactly once.
- An Eulerian circuit is an Eulerian trail that starts and ends at the same vertex.
To determine if an Eulerian trail or circuit exists:
- For an Eulerian circuit: All vertices must have even degree.
- For an Eulerian trail: Exactly two vertices must have odd degree (these will be the start and end vertices).
The degree of a vertex is the number of edges connected to it.
Hamiltonian Paths and Cycles
- A Hamiltonian path is a path that visits each vertex exactly once.
- A Hamiltonian cycle is a Hamiltonian path that returns to the starting vertex.
Unlike Eulerian trails, there's no simple rule to determine if a Hamiltonian path or cycle exists in a general graph. This leads to the famous Traveling Salesman Problem, which we'll discuss later.
Common MistakeStudents often confuse Eulerian and Hamiltonian concepts. Remember: Eulerian deals with using all edges once, while Hamiltonian deals with visiting all vertices once.
ExampleConsider the following graph with vertices:
$$V=\{A, B, C, D, E, F\}$$
and edges:
$$E=\{(A, B),(A, C),(B, D),(B, E),(C, D),(C, F),(D, E),(E, F)\}$$
A valid Hamiltonian Path for this graph could be:
$$A \rightarrow B \rightarrow E \rightarrow D \rightarrow C \rightarrow F$$
Each vertex is visited exactly once, but the path does not necessarily return to $\mathbf{A}$.
Using the same graph as above, a possible Hamiltonian Cycle is:
$$
A \rightarrow B \rightarrow E \rightarrow D \rightarrow C \rightarrow F \rightarrow A
$$
This cycle starts at A, visits every vertex exactly once, and returns to A.
Minimum Spanning Tree (MST) Algorithms
- A spanning tree of a graph is a tree that includes all vertices of the graph.
- A minimum spanning tree is a spanning tree with the lowest total edge weight.
Kruskal's Algorithm
Kruskal's algorithm finds an MST by adding the lowest-weight edge that doesn't create a cycle, until all vertices are connected.
Steps:
- Sort all edges by weight (ascending).
- Start with an empty set of edges.
- For each edge, from lowest to highest weight:
- If adding this edge doesn't create a cycle, add it.
- If it creates a cycle, skip it.
