In-Degree and Out-Degree

Graph Theory · Axiom Academy

LESSON In-Degree and Out-Degree Understanding degree concepts in directed graphs (digraphs) 1. In-Degree: Arcs Pointing In The in-degree of a vertex v, denoted deg - (v) or indeg(v), is the number of arcs that have v as their head (terminal point). These are arcs pointing into the vertex. 2. Out-Degree: Arcs Pointing Out The out-degree of a vertex v, denoted deg + (v) or outdeg(v), is the number of arcs that have v as their tail (starting point). These are arcs pointing out of the vertex. 3. The Fundamental Sum Formula A crucial property of digraphs is that the sum of all in-degrees equals the sum of all out-degrees, and both equal the total number of arcs. Vertices with zero in-degree or out-degree have special significance in directed graphs. Sources: Starting nodes in a workflow, root nodes in dependency graphs, origins in transportation networks Sinks: Terminal states in state machines, final destinations in routing, leaf nodes in directed trees 5. Balanced Vertices and Eulerian Conditions A vertex is balanced if its in-degree equals its out-degree. This concept is crucial for understanding Eulerian circuits in digraphs.

This is the written version of the interactive lesson above. See the full Graph Theory course.