22.6.2. Critical Edges

Another interesting structural property of a graph is whether or not it has cycles. An acyclic graph is a graph, such as a tree, in which you cannot start at any node and follow a sequence of edges and come back to the node. In contrast, a graph with cycles contains paths that return to the starting point.

A cycle in a graph is a path that begins and ends at the same vertex while traversing other vertices. For example, if you have vertices connected in a loop, starting at any point in the loop and following the edges will eventually lead you back to your starting point. Conversely, in a tree structure, this is impossible, as trees do not have cycles by definition.

Imagine a circular track where you can run along the path and return to the starting point. This is similar to a graph with a cycle. In contrast, think of a straight road that branches off to other straight roads. If you start at one point and don’t return along the same path, it's like being in a tree, which has no cycles.

When we execute BFS, we can keep track of the edges used to mark vertices as visited. In an acyclic graph, every node in the graph will be visited during the BFS search. However, in a graph with cycles, some edges won't be explored because when attempting to explore them, we find that the target vertex is already visited.

Non-tree edges are edges that do not form part of the tree structure generated during the BFS traversal. If an edge connects two vertices where one has already been visited, it is not utilized in the traversal. This situation signifies the presence of a cycle because it indicates a route back to an already traversed vertex.

Think of a city map where you can take several paths to reach the same destination. If you follow a specific route (like a tree edge) but find another shorter route back to the start without retracing your steps, this represents a non-tree edge and indicates that there are cycles in your journey.

In a connected acyclic graph with n vertices, there will be exactly n - 1 edges. This type of graph is known as a tree. Thus, the structure of BFS trees consists only of tree edges. Non-tree edges combined with tree edges will create a cycle.

A tree is a special type of graph that maintains connectivity without any cycles. This means that if a tree has n vertices, it can have no more than n - 1 edges. When performing BFS, the modified edges altogether form what's called a BFS tree, which is essential for quickly determining the structure of the graph. If non-tree edges are present, they indicate a potential cycle.

Consider a family tree where each person (node) is connected to their parent, with no loops indicating multiple paths to the same person. This tree structure has a specific number of connections (n - 1 edges for n members). If you were to find a situation where a relation could loop back to the same ancestor (like finding an overlap), that situation illustrates a non-tree edge.

When using DFS, we also keep track of pre and post numbers for each vertex. Each time we enter a vertex, we increment a counter as the pre-number, and upon exiting, we register the post-number. This information can also be used to classify the edges in the graph.

Using the pre- and post-numbering allows us to determine the type of edges in the graph, such as tree edges, forward edges, backward edges, and cross edges. For example, if a backward edge is found, it suggests a cycle. The pre- and post-numbers help identify the order of vertex exploration and confirm the presence or absence of cycles.

Imagine teaching a class where you keep track of when students enter and exit the classroom. The time when they enter can be seen as the pre-number and when they leave as the post-number. If a student was always returning before their exit time and confusing the counts, it signifies overlapping classes - similar to finding cycles in the graph.

In directed graphs, detecting cycles has a different approach. We must follow the direction of the edges, which can create paths leading back to a vertex. To identify cycles, we look for back edges during a DFS traversal.

In directed graphs, a cycle emerges if one can follow the directed edges around the graph and return to a starting vertex. Specifically, if a back edge is detected, it confirms the presence of a cycle. Identifying these back edges becomes crucial for understanding graph properties and analyzing their structure in-depth.

Think of following a one-way street system where some streets circle back to the starting point. If you keep reaching a traffic circle (the back edge), it signifies that you can loop indefinitely without ever leaving the area. This loop represents a cycle within a directed graph.

--