tite fractale

Graphes orientés

1. Activité introductive

1.1. Énoncé

Voir feuille (non numérisée).

1.2. Réponses

On ne cherche à coder que les destinations possibles à partir de chaque carrefour. On n’attache aucune importance à :

La seule chose qui va nous aider pour la suite, c’est de mettre deux flèches plutôt qu’une à double pointe.

1.3. Un peu de culture

Lorsque l’on joue à ces jeux, les points et les segments bougent, mais le graphe correspondant reste inchangé.

Mais a-t-on ici des graphes simples orientés ?

2. Modes de représentation

2.1. Flèches

C’est le schéma réalisé lors de l’activité, avec les flèches.

On préfèrera deux simples flèches au lieu d’une double, plus pratique pour compter le nombre de flèches.

2.2. Notation ensembliste

2.2.1. Définition d’un graphe simple orienté

Un graphe simple orienté est défini par deux ensembles $X$ et $U$.

$X = \left\{x_1, x_2, x_3,… x_n\right\}$ est un ensemble fini qui contient les sommets ou les nœuds du graphe.

$U = \left\{ (x_i, x_j),… \right\}$ est un ensemble de couples de sommets, appelés arcs (ou arêtes orientées), qui décrit les relations entre les nœuds.

Remarque :
Les couples mathématiques sont ordonnés et peuvent contenir deux fois le même objet.

2.2.2. Exemple

À partir de l’activité :

$X = \left\{ A, B, C, D \right\}$

$U = \left\{ (A, B) ; (A, C) ; (A, D) ; (B, C) ; (C, B) ; (C, D) ; (D, A) ; (D, D) \right\}$

2.2.3. Définition des successeurs et des prédécesseurs

On dit que $x_j$ est un successeur de $x_i$ si $(x_i, x_j) \in U$, autrement dit si $(x_i, x_j)$ est un arc du graphe. On note $\Gamma (x)$ l’ensemble des successeurs de $x$.

On dit que $x_i$ est un prédécesseur de $x_j$ si $(x_i, x_j) \in U$, autrement dit si $(x_i, x_j)$ est un arc du graphe. On note $\Gamma^{-1} (x)$ l’ensemble des prédécesseurs de $x$.

2.2.4. Exemples

À partir de l’activité :

On organise souvent ces informations dans des tableaux:

|  x  |  successeurs de x |       |  x  |  prédécesseurs de x |
+-----+-------------------+       +-----+---------------------+
|     |                   |       |     |                     |

2.3. Matrice

2.3.1. Définition

La matrice d’adjacence d’un graphe simple orienté à $n$ sommets est la matrice carrée $n×n$ où, si l’on note $a_{ij}$ son terme général :

2.3.2. Exemple

À partir de l’activité :

$$M = \begin{pmatrix} 0 & 1 & 1 & 1 \\\\ 0 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \\\\ 1 & 0 & 0 & 1 \\\\ \end{pmatrix}$$

2.3.3. Remarques

3. Chemins

3.1. Définitions

Dans un graphe simple orienté, on dira que :

3.2. Exemples

À partir de l’activité :

3.3. Longueur d’un chemin

3.3.1. Définition

La longueur d’un chemin à $p$ sommets (possiblement identiques) vaut $p-1$.

Autrement dit, c’est le nombre d’arcs qui le composent.

3.3.2. Propriété

3.3.2.1. Énoncé

Soit $M$ la matrice d’adjacence d’un graphe simple orienté à $n$ sommets.

Le nombre de chemins de longueur $p$ (donc à $p+1$ sommets) allant de $x_i$ à $x_j$ est le coefficient de $M^p$ se trouvant à la ligne $i$ et à la colonne $j$.

Attention, ici $M$ est considérée à coefficients entiers.

3.3.2.2. Exemples

À partir de l’activité étudions les chemins de longueur 1, puis 2, puis 3…

3.3.2.2.1. Chemins de longueur 1

D’une part, $M^1 = M$.

D’autre part, les chemins de longueur 1 sont les arcs du graphe. On retrouve bien la définition de $M$ : présence (1) ou non (0) d’un arc.

3.3.2.2.2. Chemins de longueur 2

En calculant le coefficient ligne 1 colonne 2 de $M^2$, on s’aperçoit que l’on cumule le nombre de chemins partant de A et allant vers B et passant par un seul point intermédiaire :

Par exemple, $a_{32}$ est le nombre d’arcs (0 ou 1) allant de C à B.

Le produit matriciel est donc l’outil naturel pour ce calcul.

3.3.2.2.3. Chemins de longueur 3

Un chemin de longueur 3 peut être considéré comme un chemin de longueur 2 auquel on a ajouté un arc. Si on considère les chemins de longueur 3 allant de A à D, il suffit de :

Ici on note $b_{ij}$ les coefficients de $M^2$.

On s’aperçoit que l’on calcule le coefficient à la 1ère ligne et 4ème colonne de la matrice $M^2 × M = M^3$.

On remarque aussi que l’on peut considérer $M^3 = M × M^2$.

3.3.2.2.4. Chemins de longueur 4

Idem avec $M^4 = M × M^3 = M^2 × M^2 = M^3 × M$.

4. Fermeture transitive d’un graphe et matrice d’accessibilité

4.1. Définition

La fermeture transitive d’un graphe $G$ est notée $\hat G$ (prononcé « gé chapeau » et est le graphe obtenu en :

4.2. Remarques

4.3. Exemples

  1. Donner la fermeture de l’exemples du début du cours.
  2. Soit $G$ le graphe comportant les nœuds $\left\{x_1, x_2, x_3, x_4\right\}$ et trois arcs : $\left\{(x_1, x_2), (x_2, x_3), (x_3, x_4)\right\}$.
    Donner la fermeture de ce graphe en utilisant le code couleur :
    • vert pour les arcs issus d’un chemin de longueur 2 dans $G$,
    • rouge pour les arcs issus d’un chemin de longueur 3 dans $G$,
    • bleu pour les arcs issus d’un chemin de longueur 4 dans $G$.

4.4. Calcul

Si $M$ est la matrice d’adjacence de $G$, on note $\hat M$ la matrice d’adjacence de $\hat G$, appelée la matrice d’accessibilité de $G$. On a :

$$\hat M = M \oplus M^{\left[2\right]} \oplus M^{\left[3\right]} \oplus ... \oplus M^{\left[n\right]}$$

$\oplus$ et $\left[i\right]$ sont la somme booléenne et la puissance booléenne des matrices, et $n$ la taille du graphe $G$.

4.5. Calcul avec le deuxième exemple

Calculer $M^{\left[2\right]}$, $M^{\left[3\right]}$ et $M^{\left[4\right]}$, puis les additionner avec la somme booléenne.

Remarque : Pas besoin de calculer $M^5$ car elle ne peut pas ajouter un nouvel arc. En effet, il n’y a que quatre nœuds.

5. Niveaux d’un graphe

A suivre...




Christophe Gragnic, avec l’aimable concours de JC, comme d’hab, le 09/10/2016, 16h05'28".






Page générée le 04/12/2016, 10h08'07" (source).
historique de la page
historique global

 TogetherJS