22.3. Cycles in Graphs

So, other interesting structural property of a graph is whether or not it has cycles. So, a acyclic graph is a graph such as a left, in which you cannot started at any node and follow up sequence of edges and come back to the node and their right ((Refer time: 04:29)) graph with cycles. So, for instance 5, 9 and 10 forms cycles, there are also other cycles, there are several cycles for example, 3, 4, 7, 8 has a whole form a cycle with there are also smaller cycles with in unit click 3, 4, 8 and 3, 7, 8 and 7, 8, 11 is also a cycle and so on.

A cycle in a graph is a path that starts and ends at the same vertex without retracing any edges. When we say a graph is acyclic, it means there are no such paths. In contrast, a graph that contains cycles can have paths such as the one formed by the vertices 5, 9, and 10. Additionally, cycles can involve more complex groupings of vertices, like 3, 4, 7, and 8, which together form another cycle. Recognizing cycles helps us understand the structure and complexity of a graph.

Think of cycles in a graph like a roundabout in a road network. In a road network without a roundabout (an acyclic structure), once you drive to a dead end, there’s no way back to the starting point without retracing your steps. However, in a road network with a roundabout (a cyclic structure), you can travel in a loop and return to your starting point without doubling back.

So, one of the things we can do when we execute BFS is to keep track of those edges which are actually used to mark vertices as visited... We do not need to use the edge 4, 8 when we come to 7 we do not need to use 7, 8 and so on. So, there are these edges which are left out. Now, it is easy to see that if we have a graph with n vertices and it is connected and it does not have cycles, then it will have exactly n minus 1 edges, this kind of a graph is called a tree.

When performing a Breadth-First Search (BFS), we can track which edges are used to visit new vertices. In a graph with cycles, some edges may not be used during the search because they lead to already visited vertices, indicating that the graph has a cycle. If a graph has no cycles, it will behave like a tree, which has exactly n-1 edges for n vertices. Observing this edge usage allows us to identify the presence of cycles efficiently.

Imagine you're navigating through a theme park with rides (vertices) connected by paths (edges). When you’re exploring, if you find a path that leads back to a ride you've already visited, you recognize you have a loop—this indicates a cycle. Conversely, if every time you take a new path you discover a new ride, and there are paths leading to all rides without returning, it’s like a tree structure where the rides are all distinct without loops.

So, the situation with directed graphs is little more complement, so let us see what happens when we are cycles in directed graph. So, in a directed graph we need to follow the edge arrows, arrows along the edges. So, for example, 1, 3, 4, 1 which is cycle, because we can go around without changing direction, where as 1, 6, 2, 1 is not a cycle, because and the way back have to switch directions from 2 to 1 which I cannot go.

In directed graphs, cycles are dependent on the direction of edges. A cycle exists only if you can navigate from one vertex back to itself consistently following the direction of the edges. For instance, the path from 1 to 3 to 4 and back to 1 constitutes a cycle because it respects the directed arrows. However, a path like 1 to 6 to 2 back to 1 does not form a cycle as it requires changing direction, which the arrows do not allow.

Consider a one-way street (directed edge) system in a city: if you can drive in a circuit (cycle) around several blocks without ever needing to reverse direction, you have a cycle. If you encounter a street that requires a U-turn to return to your original position, that route does not form a cycle in the directed graph of the city’s streets.

So, in order for it to complete the cycle, it must be with case that there is a path including the set which found a directed cycle... a directed graph has a cycle if and only if DFS will prevails of back edge.

There are various types of edges in directed graphs that help identify cycles. Back edges indicate that a path can go back to an earlier vertex in the traversal, thus confirming the presence of a cycle. Differentiating between tree edges, forward edges, backward edges, and cross edges helps in understanding graph structure. When a back edge is detected during a Depth-First Search (DFS), it confirms the existence of a directed cycle.

Consider a computer programming scenario where functions are called: a back edge is like a function calling another function that eventually calls back to itself. If you have functions A calling B, which in turn calls A again, you’ve created a loop or cycle. In contrast, if function A finishes without looping back, it signifies no cycle in the structure.

Now, it is important to identify cycles, because we do not have cycle we have a very nice class of graphs called directed acyclic graphs is a useful for modeling dependencies... directed acyclic graphs or DAGs soon in a later lecture.

Identifying cycles is crucial, especially in directed graphs, because when a graph is acyclic, it can model dependencies effectively. For example, if you're modeling prerequisites in education, you want to ensure that no course depends on itself indirectly, as that would create a cycle making scheduling impossible. Conversely, directed acyclic graphs (DAGs) maintain clear hierarchical structures without circular dependencies.

Think of project planning. You have tasks (vertices) that depend on prior tasks (edges). If Task A must be completed before Task B, but at the same time, Task B requires Task A, you have a cycle and a problematic planning scenario. In contrast, if the tasks can be arranged such that no task is reliant on ones that derive from it, that’s akin to having a clean path in a directed acyclic graph.

--