Definitions
Definitions Associated With Directed Graphs
Digraphs are especially important in networking, where the main
objects are collections of nodes with one-way links between them.
Many definitions from undirected
graph theory have digraph-analogues:
-
The out-degree of a vertex
is the number of edges
for all
.
-
The in-degree of a vertex
is the number of edges
for all
.
-
Recall that in undirected graphs, a walk from vertex
to a vertex is an
alternating finite sequence of vertices and edges
such that
either
or
.
-
In directed graphs, a directed walk from vertex
to a vertex is an
alternating finite sequence of vertices and edges
such that
.
-
A directed path is a directed walk which does not
repeat any vertex.
-
A directed cycle is a directed walk which does
not repeat any vertex except for the first and the last.
A good glossary of graph-theoretical definitions can be found here.
|
|