23.2.6. Indegree and Outdegree in DAGs

So, we call such a graph a directed acyclic graph, so a directed acyclic graph is just a directed graph, in which there is no directed path from any vertex back to itself.

A directed acyclic graph (DAG) is characterized by its directed edges and the absence of cycles. In a directed graph, edges have a direction, meaning they point from one vertex (or task) to another. A cycle would imply that you could start from a task and eventually return to it, which isn't allowed in a DAG. Thus, the structure ensures that you can always start from an initial task and proceed without looping back.

Think about a recipe where you must prepare ingredients in a specific order. You cannot finish the dish until you have prepared all the ingredients; you can't start cooking if you have to continually go back to prepare what's already been completed. In this way, a recipe follows a DAG structure.

Recall that for an undirected graph, we use the term degree of v to refer to the number of vertices connected to v. Now, since we have a directed graph, we separate out the degree into the indegree and the outdegree. So, the indegree is the number of edges pointing into v directed into v, the outdegree of v is a number of edges pointing out of v.

In a directed graph, we identify two types of connections for each vertex: 'indegree' and 'outdegree'. Indegree refers to the number of edges that lead into a vertex, which indicates how many tasks depend on it. Outdegree, on the other hand, represents the number of edges leading away from a vertex, showing how many tasks depend on this vertex. However, in the context of a DAG, a vertex with an indegree of 0 signifies that it can be started immediately as it has no prerequisites.

Imagine a team project where each member has their own tasks. If someone has no tasks assigned to them, they have an indegree of 0; they can start working immediately. Conversely, a member with many tasks depending on them (higher indegree) waits until others complete their tasks.

Our first claim is that every DAG has at least one vertex with indegree 0, in terms of our example a vertex with indegree 0 is something which has no dependencies.

In any directed acyclic graph, there always exists at least one vertex that has no incoming edges, which means that it has no dependencies and can be processed first. This concept can be proven by assuming that every vertex has at least one incoming edge, which would lead to a cycle. Since DAGs cannot have cycles, this assumption cannot hold, confirming the existence of at least one vertex with an indegree of 0.

Consider a class project where students can only begin their parts of the project after their peers complete theirs. If every student needs someone else's work to start, you'd end up stuck in a loop, unable to begin. Thus, at least one student (vertex) will have their task completed first with no dependencies.

Now, let us formalize this notion, so to write out a sequence of numbers which is a permutation of 1 to n in such a way that whenever there is a constraint of the form j k, that is represents edge j k, then in the numeration that we have perform j must come before k.

Topological sorting refers to arranging the vertices of a DAG in a linear order such that for every directed edge from vertex j to vertex k, j appears before k in the ordering. This ensures that you respect all the dependencies implied by the edges of the graph. The result is a valid schedule or sequence to process the tasks represented as the vertices.

Think of planning a wedding where you must follow certain schedules: You can't send invitations before booking the hall. Thus, you need to arrange tasks so that you respect the order, making sure that every step is completed before the next one can begin.

--