Project Links Logo Artwork
Graph Theory: Networking
Home > Graph Theory: Networking > Foundations > Definitions
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home


conceptsdiscoverapplycollaboratepractice
 
 
go backgo forward
go backgo forward

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:

  1. The out-degree of a vertex is the number of edges for all .
  2. The in-degree of a vertex is the number of edges for all .
  3. 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 .
  4. In directed graphs, a directed walk from vertex to a vertex is an alternating finite sequence of vertices and edges such that .
  5. A directed path is a directed walk which does not repeat any vertex.
  6. 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.

 
 
go backgo forward
go backgo forward