|
|
|
Viewing Version
3
of
'directed graph'
|
[ view 'directed graph'
|
back to history
]
| Title of object: |
directed graph |
| Canonical Name: |
DirectedGraph |
| Type: |
Definition |
| Created on: |
2002-02-03 00:17:59 |
| Modified on: |
2006-12-26 13:17:57 |
| Classification: |
msc:05C20 |
| Synonyms: |
directed graph=digraph |
Revision comment (for changes between this and next version):
| Changes for correction #11160 ('wrong sum'). |
Preamble:
% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
\input xy
\xyoption{all}
% there are many more packages, add them here as you need them
% define commands here |
Content:
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.
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{
& a \ar[r] & b \ar[d] \ar[dl] \\
& 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)\] |
|
|
|
|
|
