|
|
|
Revision difference : directed graph |
| Version 3 |
Version 2 |
| A \emph{directed graph} or \emph{digraph} is a pair $(V,E)$ where $V$ is a set of \emph{vertices} and $E$ is a subset of $V \times V$ called \emph{edges} or \emph{arcs}. |
A \emph{directed graph} or \emph{digraph} is a pair $(V,E)$ where $V$ is a set of \emph{vertices} and $E$ is a subset of $V \times V$ called \emph{edges} or \emph{arcs}. |
|
|
| If $E$ is symmetric (i.e., $(u,v) \in E$ if and only if $(v,u) \in E$), then the digraph is isomorphic to an ordinary (that is, undirected) graph. |
If $E$ is symmetric (i.e., $(u,v) \in E$ if and only if $(v,u) \in E$), then the digraph is isomorphic to an ordinary (that is, undirected) graph. |
|
|
| Digraphs are generally drawn in a similar manner to graphs with arrows on the edges to indicate a sense of direction. For example, the digraph $$\left (\{a,b,c,d\}, \{(a,b),(b,d),(b,c),(c,b),(c,c),(c,d)\}\right )$$ may be drawn as |
Digraphs are generally drawn in a similar manner to graphs with arrows on the edges to indicate a sense of direction. For example, the digraph $$\left (\{a,b,c,d\}, \{(a,b),(b,d),(b,c),(c,b),(c,c),(c,d)\}\right )$$ may be drawn as |
|
|
| $$\xymatrix{ |
$$\xymatrix{ |
| & a \ar[r] & b \ar[d] \ar[dl] \\ |
& a \ar[r] & b \ar[d] \ar[dl] \\ |
| & c \ar[ur] \ar[r] \ar@(dr,dl)[] & d \\ |
& c \ar[ur] \ar[r] \ar@(dr,dl)[] & d \\ |
| & & \\ |
& & \\ |
| }$$ |
}$$ |
|
|
| Since the graph is directed, one has the concept of the number of edges originating or terminating at a given vertex $v$. The out-degree, $d_{\textrm{out}}(v)$ of a vertex $v$ is the number of edges having $v$ as their originating vertex; similarly, the in-degree, $d_{\textrm{in}}(v)$ is the number of edges having $v$ as their terminating vertex. |
|
|
|
| Denoting by $\lvert v \rvert$ the number of vertices in the graph, obviously we have |
|
| \[\sum_{i=1}^{\lvert v\rvert} d_{\textrm{in}}(v)=\sum_{i=1}^{\lvert v\rvert} d_{\textrm{out}}(v)\] |
|
|
|
|
|
