23.2.4. Characterization of DAGs

We now turn our attention to a very interesting and important class of graphs called Directed Acyclic Graphs or DAGs.

Directed Acyclic Graphs (DAGs) are a special type of graph that allows us to model problems where tasks depend on one another. The key characteristics of these graphs are that their edges have a direction (from one vertex to another) and that there are no cycles (you can’t start at one vertex and return to it by following directed paths).

Think of a DAG like a roadmap where certain roads can be traveled only after reaching a specific intersection. You can only go from point A to point B if you first travel through point C. There are no loops on this map—once you head towards a destination, you cannot circle back to where you started.

Suppose, we are going on a foreign trip, then of course, we need a passport, we need to buy a ticket, we require a visa probably, we want to buy some travel insurance, we probably need some foreign exchange as well and perhaps you want to buy some gifts for our hosts.

When planning a foreign trip, certain tasks must be completed before others. For example, obtaining a passport is essential before buying a ticket or travel insurance. This illustrates the dependencies among tasks, which can be represented as a Directed Acyclic Graph.

Imagine you are building a Lego set. You need the base before you can add walls, and you can't add a roof until the walls are in place. Each step must be done in a specific order, much like the tasks for your trip.

So, our goal is that given these constraints in what sequence should we perform these six operations, getting a passport, buying a ticket, getting insurance, getting a visa, buying foreign exchange and buying gifts for our hosts.

The tasks for the trip are modeled as vertices in a graph. Directed edges connect these vertices based on dependencies. For instance, an edge from 'Getting Passport' to 'Buying Ticket' indicates that the passport task must be completed before the ticket can be purchased.

Like planning a recipe where you need to chop vegetables before cooking them, you can’t skip the prerequisite steps. Thus, each necessary task must be completed in a proper order, as each task depends on the previous one.

We can see that you need a passport to do anything, so we always need to start with getting a passport.

The sequencing of tasks starts with identifying which tasks have no prerequisites. By recognizing that a passport is the first step, we can begin our operations. Each subsequent operation can be done once its prerequisites are fulfilled.

It’s like building a dam: you need to excavate the site (the first task) before you can lay down the foundation for the structure. No construction can happen without having the site prepared first.

This class of graph is an important class and it has two important features, one is of course, it is directed. Because, these dependencies are from one task to another task, it is not a symmetric dependency and there are no cycles.

A crucial aspect of DAGs is that they have no cycles, meaning you cannot return to a starting point while following the direction of edges. This allows for a clear starting point and a pathway to reach the end without dead ends or contradictions.

Consider a video game that requires you to complete quests in a sequence. If one quest requires the completion of another as a prerequisite, you cannot go back to the previous quest once you finish it. The path to victory remains clear without circular routes.

What we claim; however, is that for DAGs there is no cycle, the graph is actually acyclic then we can always order it topologically.

Topological sorting refers to arranging the vertices of a DAG in a linear order respecting their dependencies. When performed, it establishes a sequence where prerequisites are always ahead of the tasks that require them.

This is similar to scheduling classes in a school; certain subjects must be taken before advanced classes can be scheduled, ensuring students have the right background knowledge before progressing.

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

In any DAG, there must be at least one task that does not depend on any other task (indegree 0). This indicates that it can be initiated at any time. The proof of this assertion hinges on the absence of cycles in the graph.

Imagine being the first player in a team who can enter the game; no prior plays are required from other colleagues before you start, allowing you to set the pace of the game.

--