22.4.2.1. Types of Edges in Directed Graphs

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, whereas 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, connections between vertices have a direction, indicated by arrows. A cycle occurs when you can start at one vertex and return to it by only following the direction of the arrows. For instance, if there's a path arrowed from vertex 1 to 3 to 4 and back to 1, a cycle forms. Conversely, if you have an arrowed path going from 1 to 6 to 2 and back to 1, it doesn't form a cycle since the path requires a change in direction that is not permitted by the arrows.

Think of a directed graph as a one-way street system in a city. If you set out from one point and can make a series of turns that leads you back to your starting point without breaking any traffic rules, that’s akin to having a cycle. If you find that to return, you have to drive the wrong way down a one-way street, then no cycle exists — just like how certain paths in a graph can't loop back under the rules of direction.

Now, if first look at these edges, the edges drawn are tree edges as before. Now, if you look at the edges that have not been part of the graph, they fall into 3 groups. So, the first type of edge which is not the part of the tree is what we call a forward edge.

When performing a Depth First Search (DFS) on a directed graph, edges can be classified into three types based on their relationship to the DFS tree formed during the traversal. Tree edges are those used to discover new vertices. Forward edges connect a vertex to a descendant in the tree, not involving any backtracking. They lead downward from parent to child in terms of DFS progression.

Imagine you are exploring a family tree. Each time you meet someone new (a 'tree edge'), you mark their relationship. If an older relative mentions a younger generation relative whose path you've already traced (a 'forward edge'), you know it connects back down but doesn't reveal new connections. This is like finding a forward edge in a graph.

The other category of edges which are not there in the tree have backward edges, they go up the tree. So, from 6 there is the edge back to 2 which we did not use, because two has already been explored.

In addition to forward edges, there are backward edges, which point from a node back to one of its ancestors in the DFS tree. These edges indicate that there is a path leading to a node that has already been explored, thereby suggesting a cycle if it backtracks in the path. This shows nodes can connect to earlier counterparts, unveiling more complex relationships in directed pathways.

Consider a game where you can move from room to room on different floors of a building. If you find a staircase leading from the third floor back to the first floor you just left, that represents a backward edge, showing you can revisit previous places, much like finding a backward edge in a graph.

Finally, there are some edges which are neither going forward nor backward, but sideways. So, these are edges like 8 to 7 and from 4 to 8.

Cross edges connect nodes across different branches of the DFS tree or between nodes that are at the same level but not directly connected in the tree structure. These edges show alternate relationships between vertices that don’t follow the strict parent-child path defined in tree edges. Cross edges help in understanding additional connections in the graph that wouldn't otherwise be visible.

Think of cross edges like shortcuts between two separate paths in a park. While you usually walk along a defined route (the tree edge), you might discover a next-door neighbor's path cuts directly across your typical route, providing a new option for travel without necessarily revisiting previous places. This offers greater connectivity options — analogous to finding cross edges.

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.

The presence of back edges is crucial for identifying cycles in a directed graph. If during the DFS, a vertex connects back to one of its ancestors through a back edge, this indicates that a cycle is present. Understanding this aids in recognizing such paths where returns happen without breaking directed rules. In a directed graph, finding a back edge is equivalent to discovering a cycle.

Imagine planning a round trip to deliver items in a neighborhood. If you start at a hub, deliver items to several houses, and find that your route allows you to revisit the hub through the same streets without detours, you have established a cyclic route. This illustrates how back edges help confirm cycles in the mapping of connections.

--