Représentation d'un graphe
La manière naïve de représenter un graphe est de noter les sommets dans le plan et de relier deux sommets par un segment ou un arc de cercle lorsque l'arête (ou l'arc) correspondant existe, en précisant par des flèches l'orientation dans le cas d'un graphe orienté. Il s'agit de la
représentation sagittale.
\[
\xymatrix@C=2cm@R=2.5cm{
a\ar[r]\ar@/^2pc/[rr]&b\ar@(ur,dr)[]&c\ar[dl]&\\
&d\ar[ul]\ar[r]\ar@/_2pc/[rr]&e\ar[ull]&f\ar[ulll]
}
\]
\( \Som(\G)=\left\{a,b,c,d,e,f\right\}\)
\( \Arc(\G)=\left\{(a,b),(a,c),(b,b),(c,d),(d,a),(d,e),\right.\)
\( \left.(d,f),(e,a),(f,a)\right\}\)
\[
\xymatrix@C=2cm@R=2.5cm{
a\ar@{-}[d]\ar@{-}[dr]\ar@{-}[drr]\ar@{-}@/^2pc/[rr]&b\ar@{-}[d]\ar@{-}[r]&c\ar@{-}[dll]\\
f&e&d
}
\]
\( \Som(\G)=\{a,b,c,d,e,f\}\)
\( \Ar(\G)=\left\{
\{a,c\},\{a,d\},\{a,e\},\{a,f\},\{b,c\},\{b,e\},\{c,f\}
\right\}\)
On peut également représenter un graphe par une matrice booléenne.
Définition
Notons \( \B=\{0,1\}\) l'algèbre de Boole standard. Son addition et sa multiplication sont données par les tables de calculs suivantes :
\[\begin{array}{c|c|c}
{\color{red} +}&0&1\\\hline
0&0&1\\\hline
1&1&1
\end{array}\qquad\qquad
\begin{array}{c|c|c}
{\color{red} \times}&0&1\\\hline
0&0&0\\\hline
1&0&1
\end{array}
\]
Le \( 0\) , \( 1\) , \( +\) et \( \times\) représentent respectivement le FAUX, VRAI, OU et ET de la logique.
Définition
Soit \( \G\) un graphe. Notons \( n\in \N_{{>}0}\) la cardinalité de \( \Som(\G)\) et notons \( \{a_1,\dots,a_n\}\) les sommets.
La
matrice booléenne ou
matrice d'adjacence de \( \G\) est une matrice \( M\in \M_{n}(\B)\) tel que
\[M_{i,j}=\left\{
\begin{array}{rl}
1 & \text{si }\{a_i,a_j\}\in \Ar(\G)\text{,}\\
0 & \text{sinon.}
\end{array}
\right.\]
Dans le cas non orienté.
\[M_{i,j}=\left\{
\begin{array}{rl}
1 & \text{si }(a_i,a_j)\in \Arc(\G)\text{,}\\
0 & \text{sinon.}
\end{array}
\right.\]
Dans le cas orienté.
Par exemple :
\[
\xymatrix@C=2cm@R=2cm{
a\ar[r]\ar@/^2pc/[rr]&b\ar@(ur,dr)[]&c\ar[dl]&\\
&d\ar[ul]\ar[r]\ar@/_2pc/[rr]&e\ar[ull]&f\ar[ulll]
}
\]
\[
\begin{array}{c|cccccc}
&a&b&c&d&e&f\\\hline
a&0&1&1&0&0&0\\
b&0&1&0&0&0&0\\
c&0&0&0&1&0&0\\
d&1&0&0&0&1&1\\
e&1&0&0&0&0&0\\
f&1&0&0&0&0&0
\end{array}
\]
\[
\xymatrix@C=2cm@R=2cm{
a\ar@{-}[d]\ar@{-}[dr]\ar@{-}[drr]\ar@{-}@/^2pc/[rr]&b\ar@{-}[d]\ar@{-}[r]&c\ar@{-}[dll]\\
f&e&d
}
\]
\[
\begin{array}{c|cccccc}
&a&b&c&d&e&f\\\hline
a&0&0&1&1&1&1\\
b&0&0&1&0&1&0\\
c&1&1&0&0&0&1\\
d&1&0&0&0&0&0\\
e&1&1&0&0&0&0\\
f&1&0&1&0&0&0
\end{array}
\]
Proposition
La matrice booléenne d'un graphe non orienté est une matrice carré symétrique à diagonale nulle.
Démonstration
Si \( \{a_i,a_j\}\) est une arête alors \( \{a_j,a_i\}\) également (l'ordre des éléments dans un ensemble ne compte pas). De plus \( \{a_i, a_i\}\) ne peut jamais être une arête (les arêtes sont des ensembles à deux éléments or \( \{a_i, a_i\}=\{a_i\}\) ).
Définition
Soit \( \G\) un graphe orienté. On note \( \nonor{\G}\) le graphe non orienté associé à \( \G\) et défini par :
\[\Som(\nonor{\G})=\Som(\G),\qquad\Ar(\nonor{\G})=\left\{\{x,y\}\big|x\neq y \wedge (x,y)\in Arc(\G)\right\}\]
Pour "désorienter" un graphe, il suffit d'enlever les boucles et les flèches de sa représentation sagittale.
\[
\xymatrix@C=2cm@R=2cm{
a\ar[r]\ar@/^2pc/[rr]&b\ar@(ur,dr)[]&c\ar[dl]&\\
&d\ar[ul]\ar[r]\ar@/_2pc/[rr]&e\ar[ull]&f\ar[ulll]
}
\]
\[
\xymatrix@C=2cm@R=2cm{
a\ar@{-}[r]\ar@/^2pc/@{-}[rr]&b&c\ar@{-}[dl]&\\
&d\ar@{-}[ul]\ar@{-}[r]\ar@/_2pc/@{-}[rr]&e\ar@{-}[ull]&f\ar@{-}[ulll]
}
\]
Pour la représentation matricielle, le procédé est un peu plus compliqué : il faut tout d'abord mettre des \( 0\) sur la diagonale (ce qui correspond à enlever les boucles) et rendre la matrice symétrique.
\[
\begin{array}{c|cccccc}
&a&b&c&d&e&f\\\hline
a&0&1&1&0&0&0\\
b&0&1&0&0&0&0\\
c&0&0&0&1&0&0\\
d&1&0&0&0&1&1\\
e&1&0&0&0&0&0\\
f&1&0&0&0&0&0
\end{array}\quad\Longrightarrow
\]
\[
\begin{array}{c|cccccc}
&a&b&c&d&e&f\\\hline
a&0&1&1&0&0&0\\
b&0&\color{red}{0}&0&0&0&0\\
c&0&0&0&1&0&0\\
d&1&0&0&0&1&1\\
e&1&0&0&0&0&0\\
f&1&0&0&0&0&0
\end{array}\quad\Longrightarrow
\]
\[
\begin{array}{c|cccccc}
&a&b&c&d&e&f\\\hline
a&0&1&1&\color{red}{1}&\color{red}{1}&\color{red}{1}\\
b&\color{red}{1}&0&0&0&0&0\\
c&\color{red}{1}&0&0&1&0&0\\
d&1&0&\color{red}{1}&0&1&1\\
e&1&0&0&\color{red}{1}&0&0\\
f&1&0&0&\color{red}{1}&0&0
\end{array}\qquad\qquad
\]
