What is a Graph? · Definitions

Lesson 8

Nikolai Chukhin · Alexander S. Kulikov

Now, assume that the graph \(G(V,E)\) is directed and use the following as a working toy example: \[V=\{A, B, C, D\} \text{ and }E=\{(A, B), (B, C), (C, D), (B, D), (A, D), (D, A)\}.\]

For directed graphs, one distinguishes between incoming degree and outgoing degree of a node called, respectively, indegree and outdegree: \[\begin{align*}\operatorname{indeg}(v)&=|\{u \in V \colon (u, v) \in E\}|,\\ \operatorname{outdeg}(v)&=|\{u \in V \colon (v, u) \in E\}|.\end{align*}\] For example, \[\operatorname{indeg}(A)=1,\ \operatorname{outdeg}(A)=2,\ \operatorname{indeg}(D)=3,\ \operatorname{outdeg}(D)=1.\]

from networkx import DiGraph

graph = DiGraph(['AB', 'BC', 'AD', 'BD', 'CD', 'DA'])

for node in ('A', 'D'):
    print(f'indeg({node})={graph.in_degree(node)}', end=' ')
    print(f'outdeg({node})={graph.out_degree(node)}', end=' ')

indeg(A)=1 outdeg(A)=2 indeg(D)=3 outdeg(D)=1

Walks, paths, and cycles in directed graphs are defined similarly to the undirected case, but they need to respect the directions on edges. For example, \(B \to D \to C\) is not a walk in the toy graph above, since there is no edge \((D,C)\) in the graph.