24.1.1. Introduction to In Degrees

So, let us apply the strategy to this DAG, so we first begin by labelling every vertex by its in degree. So, we have indicated the in degree of every vertex. So, for instance 1 and 2 have no incoming edges. So, they have in degree 0, vertex 3 has 2 edges coming in and in degree 2, vertex 8 has 4 edges coming inside and in degree as 4 and so on.

In a Directed Acyclic Graph (DAG), each vertex can have incoming edges that determine its in degree. The in degree is simply the count of how many edges are directed towards a vertex. For example, if vertex 1 and vertex 2 have no edges pointing to them, their in degree is 0. Vertex 3 has 2 edges leading to it, resulting in an in degree of 2, while vertex 8 has 4 edges pointing towards it, giving it an in degree of 4.

Think of in degree like the number of invitations received for a party. If you're hosting a party and no one invites you, your in degree is 0. If 2 people invite you, your in degree goes up to 2. Similarly, if 4 people invite you, it goes to 4. The more invitations (incoming edges) you have, the higher your in degree.

Now we have to pick up a vertex of in degree 0 enumerated and eliminated. So, we have a choice between 1 and 2, so let us suppose we start with 1. When we eliminate it, we also eliminate the edges going out of it. The edges coming into 3, 4, and 5 will reduce by 1 because vertex 1 is gone.

After determining the in degrees, we look for vertices that have an in degree of 0. In this case, we can choose vertex 1 or vertex 2. Let's say we choose vertex 1. By selecting and eliminating vertex 1, we not only remove the vertex itself but also decrease the in degree of the vertices that had edges directed from vertex 1 (which are vertices 3, 4, and 5) by 1.

Imagine vertex 1 is a person who organized a group project. When this person leaves the project (is eliminated), anyone who depended on them (vertices 3, 4, and 5) now needs to adjust their tasks since they can no longer rely on person 1's input. This adjustment reduces their workload (in degree) by 1.

What happens on eliminating 1 is that we reduce the in degrees of 3, 4, and 5 from 2, 1, 1 to 1, 0, 0.

After eliminating vertex 1, we see that the in degrees of vertices 3, 4, and 5 are updated. If their initial in degrees were 2, 1, and 1 respectively, they are now adjusted to 1, 0, and 0. This reflects that one less edge points to vertex 3, while vertex 4 has no incoming edges left, hence it now has an in degree of 0.

Think of it like a class project where a student (vertex 1) has left the group. The remaining tasks (vertices 3, 4, and 5) now have fewer dependencies. If initially, task 3 required help from two students, after one student leaves, only one help is needed, hence the adjustment in the task's 'incoming help requests' (in degree). Task 4 no longer requires help from the student who left, meaning it can now be done independently.

We can choose any of the original vertices with in degree 0, which are now available. After choosing vertex 4, the in degrees of 6 and 8 also need to be updated. For instance, eliminating vertex 4 reduces the in degree of vertex 6 from 2 to 1.

Once we have modified the previous vertices, we can continue to choose any vertex that now has an in degree of 0. For instance, after eliminating vertex 4, we need to adjust the in degrees of vertices that depend on it, such as vertex 6 which now has one less edge pointing towards it. The in degrees are continuously updated to reflect the current state of the graph.

Going back to our class project analogy, after eliminating one student (vertex 1) and another task (vertex 4) that they were responsible for, the workload for other students (like task 6) becomes easier. If one student was dependent on two others for help, now that dependency is lessened as one of them is no longer part of the group.

After proceeding through the elimination of available vertices, eventually we reach a point where we can only eliminate vertex 3, and this forms a valid topological ordering.

As the process continues, we keep eliminating vertices with an in degree of 0. By carefully choosing and eliminating vertices, we eventually arrive at a realistic topological order for completion. This means that every vertex has been processed in a sequence that respects the directed edges of the graph.

This can be compared to completing a series of assignments where each subsequent task is dependent on the completion of the previous one. Each task represents a vertex, and as you complete each one, you create an organized list of tasks completed, ensuring that prerequisite tasks are finished before moving on.

--