Graph Concepts

Digraphs and weighted graphs

digraph Graphs that have arrows added to each edge are called directed graphs or digraphs (pronounced "DYE-graphs"). The arrows show that the edge has a direction associated with it. (Multigraphs and pseudographs may also be directed.)
The indegree of a vertex in a digraph is the number of edges entering (pointing to) that vertex. The outdegree of the vertex is the number of edges leaving (pointing away from) that vertex.

Sometimes a digraph is called an oriented graph. The simple graph from which the digraph is drawn is called the underlying graph. Sometimes a digraph is referred to as an orientation of the underlying graph.
In addition, an edge can be referred to as oriented or having an orientation. In graph theory, either all or none of the edges of a graph will be oriented.

identical underlying graphs We say that a digraph is strongly connected when, for every vertex u, there exists a path that follows directed edges from u to all the other vertices in the graph. Note, however, that the path must travel in the direction of the orientation of the edges. The two digraphs to the left have the same underlying graph. The first digraph is strongly connected, and the second one is not because there is no path from A to C. It is always possible to orient the edges of a graph that is connected so that the resulting digraph is not strongly connected.

weighted graph In this graph, each edge is labeled with a numerical value or weight. Graphs that have this additional information are called weighted graphs. Multigraphs and pseudographs may also be weighted.

A network is a weighted digraph. (A few authors use the term network to refer to any weighted graph or even to any graph.)

	Graphs that have arrows added to each edge are called directed graphs or digraphs (pronounced "DYE-graphs"). The arrows show that the edge has a direction associated with it. (Multigraphs and pseudographs may also be directed.) The indegree of a vertex in a digraph is the number of edges entering (pointing to) that vertex. The outdegree of the vertex is the number of edges leaving (pointing away from) that vertex.
Sometimes a digraph is called an oriented graph. The simple graph from which the digraph is drawn is called the underlying graph. Sometimes a digraph is referred to as an orientation of the underlying graph. In addition, an edge can be referred to as oriented or having an orientation. In graph theory, either all or none of the edges of a graph will be oriented.
	We say that a digraph is strongly connected when, for every vertex u, there exists a path that follows directed edges from u to all the other vertices in the graph. Note, however, that the path must travel in the direction of the orientation of the edges. The two digraphs to the left have the same underlying graph. The first digraph is strongly connected, and the second one is not because there is no path from A to C. It is always possible to orient the edges of a graph that is connected so that the resulting digraph is not strongly connected.
	In this graph, each edge is labeled with a numerical value or weight. Graphs that have this additional information are called weighted graphs. Multigraphs and pseudographs may also be weighted.