next up previous
suivant: Matrices associées aux graphes monter: Introduction précédent: Les graphes non orientés

Cocycles, degrés

Soit $ G=(X,\,E)$ un graphe orienté. On appelle cocycle d'un sommet l'ensemble des sommets qui lui sont adjacents ou l'ensemble des arcs qui lui sont incidents. On note :

\begin{displaymath}
\left\{
\begin{array}{lcll}
\Gamma^+(i)&=&\left\{ j\in X ...
...nsemble
des prédécesseurs de $i$} \\
\end{array}
\right.
\end{displaymath}

Les cocycles $ \Gamma$ sont des cocycles de sommets, alors que les cocycles $ \omega$ sont des cocycles d'arcs. Les deuxièmes se révèlent beaucoup plus utiles dans le cas général. Si nous reprenons le graphe de la figure (1.1), nous avons, par exemple :

\begin{displaymath}
\left\{
\begin{array}{lcl}
\Gamma^+(2)&=&\{1\,;\,2\,;\,3\...
...\}\\
\omega^-(3)&=&\{d\,;\,e\,;\,f\}
\end{array}
\right.
\end{displaymath}

Dans le cas non orienté, l'on a $ \Gamma^+=\Gamma^-=\Gamma$ et, réciproquement, $ \omega^+=\omega^-=\omega$. Notons qu'il existe un autre système de notation :

\begin{displaymath}
\left\{
\begin{array}{lcl}
\Gamma^+ & \Leftrightarrow & \...
...amma^- & \Leftrightarrow & \Gamma^{-1}
\end{array}
\right.
\end{displaymath}

Les degrés sont des quantités attachées au sommet et qui expriment la cardinalité des cocycles. On notera :

\begin{displaymath}
\left\{
\begin{array}{lclcll}
d_G^+(i) &=& \vert\Gamma^+(...
...ou degré entrant de
$i$ dans $G$} \\
\end{array}
\right.
\end{displaymath}

En gros, le demi degré extérieur compte le nombre d'arcs qui sortent d'un sommet alors que le demi degré intérieur compte le nombre d'arcs qui entrent en un sommet. On appelle degré du sommet $ i$ et l'on note $ d_G(i)=d_G^+(i)+d_G^-(i)$. Dans le cas non orienté, l'on a : $ d_G(i)=d_G^+(i)=d_G^-(i)$ Si l'on revient au cas orienté, on a un résultat intéressant. Soit $ G=(X,\,E)$, on a :

$\displaystyle \sum_{i\in X}d_G^+(i)=\sum_{i\in X}d_G^-(i)
$

car chaque arc possède exactement une extrémitié initiale et une extrémité finale. D'où :

$\displaystyle \sum_{i\in X}d_G^+(i)\;=\;\sum_{i\in X}d_G^-(i)\;=\;m
$

avec $ m$ nombre d'arcs du graphe. Finalement :

$\displaystyle d(G)=\sum_{i\in X}d_G^+(i)\;+\;\sum_{i\in X}d_G^-(i)\;=\;2m
$


\begin{defi}[Graphe complet]
On qualifie de \emph{complet} un graphe orienté te...
...i,\,j)$\ pour chaque couple de sommets $(i,\,j)\:\in\:X\,\times\,X$.
\end{defi}

\begin{defi}[Graphe vide]
On appelle graphe vide tout graphe qui ne contient aucun arc ou aucune arête.
\end{defi}

next up previous
suivant: Matrices associées aux graphes monter: Introduction précédent: Les graphes non orientés
Bruno Garcia 2000-12-17