Graphes
Introduction
Métriques sur les graphes
Sommets adjacents et graphe complet
Implémentation en Python
Les différents parcours
Powered by Mathigon

Share

Reset Progress

This will delete your progress and chat data for all chapters in this course, and cannot be undone!

Glossary

Select one of the keywords on the left…

GraphesSommets adjacents et graphe complet

Reading time: ~25 min

Il faut maintenant trouver un moyen de décrire les graphes.

Pour cela on peut utiliser une matrice d'adjacence.

Sommets adjacents

Deux sommets sont adjacents s'ils sont reliés par une arête.

Exercice

Dans le graphe ci-dessus, le sommet C est adjacent au sommet

Le voisinage d'un sommet est l'ensemble des sommets qui lui sont adjacents.

Sélectionner tous les sommets qui sont dans le voisinage du sommet C.

svg.graph(height=240 width=240 style='margin: 0 auto .8em')

Graphe complet

Un graphe est dit complet lorsque tous ses sommets sont adjacents.

Exercice

Parmis les graphes ci-dessous, le graphe est complet.

Graphe A

Graphe B

Graphe C

Graphe D

Matrice d'adjacence

Une matrice d'ajacence est une matrice (une sorte de tableau à deux dimensions) qui représente les relations d'ajacences entre 2 sommets.

Exemple : Construire une matrice d'adjacence

Dans cet exemple, nous allons construire pas à pas, le début de la matrice d'adjacence liée au graphe ci-dessous.

Dans la première ligne de notre matrice, on met les relations du sommet A avec les sommets du graphe.

\begin{pmatrix} \textcolor{red}{\bf \dots} & \textcolor{red}{\bf \dots} & \textcolor{red}{\bf \dots} &  \textcolor{red}{\bf \dots} \  \dots & \dots & \dots & \dots \ \dots & \dots & \dots & \dots \ \dots & \dots & \dots & \dots \ \end{pmatrix}

Le sommet A n'est pas relié à lui même. On met donc un 0 en 1ère ligne, 1ère colone \begin{pmatrix} \textcolor{red}{\bf 0} & {\bf \color{red!60} \dots} & \mathbf{\dots} &  {\bf \dots} \  \dots & \dots & \dots & \dots \ \dots & \dots & \dots & \dots \ \dots & \dots & \dots & \dots \ \end{pmatrix}

Le point A est relié avec le point B. On met donc un 1 en 1ère ligne, 2ème colone. \begin{pmatrix} 0 & \textcolor{red}{\bf 1} & {\bf \dots} &  {\bf \dots} \  \dots & \dots & \dots & \dots \ \dots & \dots & \dots & \dots \ \dots & \dots & \dots & \dots \ \end{pmatrix}

Le point A est relié avec le point C. On met donc un 1 en 1ère ligne, 3ème colone. \begin{pmatrix} 0 & 1 & \textcolor{red}{\bf 1} &  \dots \  \dots & \dots & \dots & \dots \ \dots & \dots & \dots & \dots \ \dots & \dots & \dots & \dots \ \end{pmatrix}

Le point A est relié avec le point D. On met donc un 1 en 1ère ligne, 4ème colone. \begin{pmatrix} 0 & 1 & 1 &  \textcolor{red}{\bf 1} \  \dots & \dots & \dots & \dots \ \dots & \dots & \dots & \dots \ \dots & \dots & \dots & \dots \ \end{pmatrix}

Dans la seconde ligne de notre matrice, on met les relations du sommet B avec les sommets du graphe. \begin{pmatrix} 0 & 1 & 1 & 1 \\  \textcolor{red}{\bf \dots} & \textcolor{red}{\bf \dots} & \textcolor{red}{\bf \dots} & \textcolor{red}{\bf \dots} \  \dots & \dots & \dots & \dots \  \dots & \dots & \dots & \dots \  \end{pmatrix}

Le point B est relié avec le point A. On met donc un 1 en 2ème ligne, 1ère colone. \begin{pmatrix} 0 & 1 & 1 & 1 \\  \textcolor{red}{\bf 1} & \dots & \dots & \dots \  \dots & \dots & \dots & \dots \  \dots & \dots & \dots & \dots \  \end{pmatrix}

Le point B n'est pas relié à lui-même. On met donc un 0 en 2ème ligne, 2ème colone. \begin{pmatrix} 0 & 1 & 1 & 1 \\  1 & \textcolor{red}{\bf 0} & \dots & \dots \  \dots & \dots & \dots & \dots \  \dots & \dots & \dots & \dots \  \end{pmatrix}

Le point B est relié au point C. On met donc un 1 en 2ème ligne, 3ème colone. \begin{pmatrix} 0 & 1 & 1 & 1 \\  1 & 0 & \textcolor{red}{\bf 1} & \dots \  \dots & \dots & \dots & \dots \  \dots & \dots & \dots & \dots \  \end{pmatrix}

Le point B n'est pas relié au point D. On met donc un 0 en 2ème ligne, 4ème colone. \begin{pmatrix} 0 & 1 & 1 & 1 \\  1 & 0 & 1 & \textcolor{red}{\bf 0} \  \dots & \dots & \dots & \dots \  \dots & \dots & \dots & \dots \  \end{pmatrix}

Pour la 3ème ligne on regarde les connexions du point C. \begin{pmatrix} 0 & 1 & 1 & 1 \\  1 & 0 & 1 & 0 \  \textcolor{red}{\bf 1} & \textcolor{red}{\bf 1} & \textcolor{red}{\bf 0} & \textcolor{red}{\bf 0} \  \dots & \dots & \dots & \dots \  \end{pmatrix}

Pour la dernière ligne on regarde les connexions du point D. On remarque que le point D est relié à lui-même, d'où le 1 dans la 4ème ligne et 4ème colone. \begin{pmatrix} 0 & 1 & 1 & 1 \\  1 & 0 & 1 & 0 \ 1 & 1 & 0 & 0 \  \textcolor{red}{\bf 1} & \textcolor{red}{\bf 0} & \textcolor{red}{\bf 0} & \textcolor{red}{\bf 1} \  \end{pmatrix}

Maintentant que tu à compris le fonctionnement, exerce-toi avec le graphe ci-dessous.

Exercice

Complète la matrice d'adjacence liée au graphe ci-dessous.

−−−−−−

Matrice d'adjacence & graphe orienté

Pour les graphes orientés, on procède de la même manière. Si le coefficient aij=1, il y a un arc qui relie le sommet i au sommet j

Par exemple :

La matrice d'adjacence liée à ce graphe est :

\begin{pmatrix} 0&1&0&0&1&0&0 \ 0&0&1&1&0&0&0 \ 0&0&0&1&0&0&0 \ 0&0&0&0&1&0&0 \\ 0&0&0&0&0&0&0 \ 0&0&0&0&1&0&1 \ 0&0&0&0&1&1&0 \end{pmatrix}

Exercice

Déterminer la matrice d'adjacence du graphe ci-dessous :

Matrice d'adjacence & graphe pondéré

Pour les graphes pondéré, les coefficients de la matrice correspond au poids des arêtes.

La matrice d'adjacence liée à ce graphe est :

\begin{pmatrix} 0&2&0&0&0 \ 2&0&4&5&0 \ 0&4&0&1&1 \ 0&5&1&0&3 \ 0&0&1&3&0 \end{pmatrix}

Déterminer la matrice d'adjacence du graphe ci-dessous :

Archie