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 :

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

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 :

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

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 :

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

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

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

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 :

$$\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ù :

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

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

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