Degrés
Définition
Soient \( \G\) un graphe et \( x\in \Som(\G)\) . On appelle \( d^{+1}(x,\G)=\Card(\Gamma^{+1}(x,\G))\) le demi-degré extérieur de \( x\) et \( d^{-1}(x,\G)=\Card(\Gamma^{-1}(x,\G))\) le demi-degré intérieur de \( x\) .
Lorsque le graphe est non orienté \( d^{+1}(x,\G)=d^{-1}(x,\G)\) que l'on note simplement \( d^1(x,\G)\) et que l'on appelle le degré de \( x\) .
Remarque
Les demi-degrés représentent les nombres de successeurs et prédécesseurs.
Remarque
On devine aisément ce que serait les définitions de \( d^{+n}(x,\G)\) , \( d^{-n}(x,\G)\) et \( d^n(x,\G)\) . Nous ne les utiliserons pas cependant.
Proposition [(Formule des degré)]
Soit \( \G\) un graphe orienté.
\[\sum_{x\in \Som(\G)}d^{+1}(x,\G)=\sum_{x\in \Som(\G)}d^{-1}(x,\G)=\Card(\Arc(\G))\]
Démonstration
Notons \( M\) la matrice booléenne du graphe \( \G\) , \( n\) le nombre de sommet et \( \{a_1,\dots, a_n\} \) les sommets.
Le nombre de \( 1\) dans la ligne \( i\) indique le nombre de successeurs au sommet \( a_i\) et le nombre de \( 1\) dans la colonne \( j\) indique le nombre de prédécesseurs au sommet \( a_j\) . Autrement \( \dpl{d^{+1}(a_i,\G)=\sum_{j=1}^nM_{i,j}}\) et \( \dpl{d^{-1}(a_j,\G)=\sum_{i=1}^nM_{i,j}}\) où les sommes se réalisent dans \( \N\) .
On observe de plus que le nombre total de \( 1\) dans la matrice correspond aux nombre d'arc du graphe. Ainsi
\begin{eqnarray*}
\Card(\Arc(\G))&=&\sum_{i=1}^n\sum_{j=1}^n M_{i,j}\\
&=&\sum_{i=1}^n\left(\sum_{j=1}^n M_{i,j}\right)=\sum_{i=1}^nd^{+1}(a_i,\G)\\
&=&\sum_{j=1}^n\left(\sum_{i=1}^n M_{i,j}\right)=\sum_{j=1}^nd^{-1}(a_j,\G)\\
\end{eqnarray*}
Proposition [(Formule des degrés)]
Soit \( \G\) un graphe non orienté.
\[\sum_{x\in \Som(\G)}d^1(x,\G) = 2\Card(\Ar(\G))\]
Démonstration
Soient \( n\) le nombre de sommet de \( \G\) , \( \{a_1,\dots,a_n\}\) les sommets de \( \G\) et \( M\) la matrice booléenne de \( \G\) . Le nombre de \( 1\) sur la ligne \( i\) donne le nombre de sommet adjacent à \( a_i\) . Autrement dit
\( \dpl{d^1(a_i,\G)=\sum_{j=1}^nM_{i,j}}\)
où la somme s'effectue dans \( \N\) et non dans \( \B\) . De plus le nombre total de \( 1\) dans la matrice vaut \( 2\Card(\Ar(\G))\) car si \( \{a_i,a_j\}\) est une arête de \( \G\) c'est également le cas de \( \{a_j,a_i\}\) . Alors
\[
2\Card(\Ar(\G))=\sum_{i=1}^n\sum_{j=1}^nM_{i,j}
=\sum_{i=1}^n\left(\sum_{j=1}^nM_{i,j}\right)
=\sum_{i=1}^nd^1(a_i,\G).\]
Corollaire
Dans un graphe non orienté le nombre de sommet de degré impair est pair.
Démonstration
La somme de tous les degrés d'un graphe non orienté peut se décomposer en la somme des sommets de degré pair plus la somme des sommets de degré impair
\[\sum_{x\in \Som(\G)}d(x,\G)=\sum_{\overset{x\in \Som(\G)}{d(x,\G)\text{ pair}}} d(x,\G) + \sum_{\overset{x\in \Som(\G)}{d(x,\G)\text{ impair}}} d(x,\G)\]
D'après la proposition précédente cette somme est pair. De plus \( \dpl{\sum_{\overset{x\in \Som(\G)}{d(x,\G)\text{ pair}}} d(x,\G)}\) est pair (puisque dans cette somme tous les \( d(x,\G)\) sont pair) alors nécessairement \( \dpl{ \sum_{\overset{x\in \Som(\G)}{d(x,\G)\text{ impair}}} d(x,\G)}\) est pair.
Puisque dans cette dernière somme tous les \( d(x,\G)\) sont impairs ils sont forcement en nombre pair (une somme impair de nombre impair est impair et une somme pair de nombre impair est pair1).
Corollaire
Soit \( \G\) un graphe non orienté connexe,
\[\Card(\Ar(\G))\geqslant \Card(\Som(\G))-1\]
Démonstration
Soit \( n=\Card(\Som(\G))\) . On va raisonner par récurrence sur \( n\in \N_{{>}0}\) , le cas initial étant trivial. On observe pour commencer pour tout sommet \( x\) de \( \G\) , \( d^1(x,\G)\geqslant 1\) car le graphe est connexe.
- \( \bullet\)
- Soit \[\exists x_0\in \Som(\G), \ d^{1}(x_0,\G)=1\]
Dans ce cas on considère le graphe \( \G'\) défini comme le sous-graphe de \( \G\) engendré par \( \Som(\G)-\{x_0\}\) qui est connexe par construction.
\begin{eqnarray*}
\Card(\Ar(\G)) &=&\Card(\Ar(\G'))+1\\
&\geqslant&\Card(\Som(\G'))-1+1\\
&\geqslant&\underbrace{\Card(\Som(\G'))+1}-1\\
&\geqslant&\Card(\Som(\G))-1.
\end{eqnarray*}
- \( \bullet\)
- Soit \[\lnot(\exists x_0\in \Som(\G), \ d^{1}(x_0,\G)=1) = (\forall x\in \Som(\G), \ d^1(x,\G){>}1) = (\forall x\in \Som(\G), \ d^1(x,\G)\geqslant 2)\]
Dans ce cas, en utilisant la formule des degrés,
\begin{eqnarray*}
\Card(\Ar(\G)) &=& \frac{1}{2}\sum_{x\in \Som(\G)}d^1(x,\G) \\
&\geqslant& \frac{1}{2}\sum_{x\in \Som(\G)}2 \\
&\geqslant& \sum_{x\in \Som(\G)}1 \\
&\geqslant& \Som(\G) \\
&\geqslant& \Som(\G)-1
\end{eqnarray*}
Définition
- \( (i)\)
- On dira qu'un graphe non orienté connexe \( \G\) est un arbre si \( \dpl{\Card(\Ar(\G))= \Card(\Som(\G))-1}\) .
- \( (ii)\)
- Un graphe non orienté sera une forêt si chacune de ses composantes connexes est un arbre.
Voici une forêt.
\[
\xymatrix@C=0.2cm@R=0.5cm{
\bullet\\
\bullet\ar@{-}[u]
}
\]
\[
\xymatrix@C=0.1cm@R=0.5cm{
&&&&&&&\bullet&\bullet&\bullet\\
&&\bullet&&&\bullet&&&\bullet\ar@{-}[r]\ar@{-}[u]\ar@{-}[ul]\ar@{-}[ur]&\bullet\\
&&\bullet\ar@{-}[u]&&\bullet&\bullet\ar@{-}[u]&&\bullet\ar@{-}[ur]&\bullet\ar@{-}[u]&\\
&\bullet\ar@{-}[ur]&&\bullet\ar@{-}[ul]\ar@{-}[ur]&&&\bullet\ar@{-}[ul]\ar@{-}[ur]\ar@{-}[d]&&&\\
\bullet&&\bullet&&&&&&&\bullet\\
&\bullet\ar@{-}[ul]\ar@{-}[ur]\ar@{-}[r]&\bullet\ar@{-}[r]&\bullet\ar@{-}[uu]&&&\bullet\ar@{-}[uu]\ar@{-}[rr]&&\bullet\ar@{-}[r]\ar@{-}[ur]&\bullet\\
&&\bullet\ar@{-}[u]&&&\bullet\ar@{-}[ur]\ar@{-}[ull]&&&&\\
&&&&&&&&&\\
&&&&&&&&&\\
&&&&&\bullet\ar@{-}[uuu]&&&&
}
\]
\[
\xymatrix@C=0.2cm@R=0.5cm{
\bullet\ar@{-}[rd]&&\bullet\ar@{-}[ld]\\
&\bullet\ar@{-}[d]&\\
&\bullet&}
\]
\[
\xymatrix@C=0.2cm@R=0.5cm{
&&\bullet&\\
\bullet&&\bullet\ar@{-}[u]\ar@{-}[r]&\bullet\\
&\bullet\ar@{-}[ul]\ar@{-}[ur]&&\\
&\bullet\ar@{-}[u]&&
}
\]
Définition
Soit \( \G\) un graphe.
- \( (i)\)
- On dira que \( \G\) possède un circuit s'il existe \( \alpha\in \Chain(\G)\) tel que \( \norm{\alpha}{>}0\) et \( or(\alpha)=ab(\alpha)\) .
- \( (ii)\)
- Dans le cas contraire on dira que le graphe est sans circuit.
Un circuit correspond à une chaine "qui boucle".
\[\xymatrix@C=2cm@R=1cm{
&a\ar[dl]&b\ar[dd]\ar[lld]&\\
f\ar[rrd]&&&c\ar@/_2pc/[llu]\ar@/^2pc/[lld]\\
&e\ar@/^7pc/[uu]\ar[lu]\ar[ruu]\ar[r]&d&
}\]
Ce graphe est sans circuit.
Définition
Une chaine eulérienne d'un graphe \( \G\) est une chaine qui passe une et une seule fois par toutes les arêtes (ou arc) de \( \G\) .
Un circuit eulérien d'un graphe est une chaine eulérienne qui est un circuit.
Théorème
Un graphe connexe admet un circuit eulérien si et seulement si :
- Cas non orienté :
- pour tous les sommets \( x\) de \( \G\) , \( d^1(x,\G)\) est paire.
- Cas orienté :
- pour tout les sommets \( x\) de \( \G\) , \( d^{+1}(x,\G)=d^{-1}(x,\G)\) .
Corollaire
Soient \( a\) et \( b\) deux sommets d'un graphe connexe \( \G\) . Il existe une chaine eulérienne entre \( a\) et \( b\) si et seulement
- Cas non orienté :
- \( d^{1}(a,\G)\) et \( d^{1}(b,\G)\) sont impaires et les degrés de tous les autres sommets sont paires.
- Cas orienté :
- \( d^{+1}(a,\G)=d^{-1}(a,\G)+1\) , \( d^{+1}(b,\G)=d^{-1}(b,\G)-1\) et pour tout \( x\in \Som(\G)-\{a,b\}\) , \( d^{+1}(x,\G)=d^{-1}(x,\G)\) .
1Et une somme impair de nombre pair élevé à une puissance pair puis divisée par la moitié d'elle même donne un nombre dont le quart du double vaut 1.
