24.1.2. Elimination Process

Try these first

1. 1.

   Define in-degree.

   Hint

   Think about how edges connect vertices.

2. 2.

   What happens to the in-degree of vertices when a vertex with in-degree 0 is removed?

   Hint

   Consider the connections or outgoing edges.

3. 3.

   What does in-degree represent in a graph?

   • Count of outgoing edges
   • Count of incoming edges
   • Total edges connected

   Hint

   Focus on how edges approach the vertex.

4. 4.

   True or False: The removal of a vertex does not affect the connected vertices' in-degrees.

   • True
   • False

   Hint

   Consider how vertices are interconnected.

5. 5.

   Given a DAG with edges (1->2, 2->3, 1->3), what is the sequence of eliminations starting from in-degree zero vertices?

   Hint

   Trace the edges to visualize which vertices connect.

6. 6.

   Illustrate the effects of removing vertex 4 from a graph where the in-degrees of its neighbors become 0. What would be the next valid removal?

   Hint

   Focus on how the dependencies change.