Graphes et matrices - Expert
Matrice d'adjacence d'un graphe
Exercice 1 : Trouver le nombre chromatique d'un graphe particulier
Quel est le nombre chromatique de ce graphe ?
Exercice 2 : Bac ES 2015 métropole - Exercice 2 spécialité - Graphes
Partie 1
On considère le graphe \(\mathcal{G}\) ci-dessous :
On s'intéresse maintenant au graphe \(\mathcal{G}'\) ci-dessous.
On note \(M\) la matrice d'adjacence associée à ce graphe en prenant les sommets dans l'ordre alphabétique
On donne : \[M^3 = \begin{pmatrix}8 & 8 & 8 & 4 & 8 & 10 & 8 & 10\\8 & 2 & 2 & 2 & 2 & 6 & 2 & 4\\8 & 2 & 2 & 2 & 2 & 4 & 2 & 6\\4 & 2 & 2 & 0 & 2 & 6 & 2 & 6\\8 & 2 & 2 & 2 & 2 & 4 & 2 & 6\\10 & 6 & 4 & 6 & 4 & 4 & 6 & 4\\8 & 2 & 2 & 2 & 2 & 6 & 2 & 4\\10 & 4 & 6 & 6 & 6 & 4 & 4 & 4\end{pmatrix}\]
Partie 2
On s'appuiera sur l'étude réalisée dans la partie 1 pour répondre aux questions de la partie 2.
Un club alpin souhaite proposer à ses membres des randonnées de plusieurs
jours dans les Alpes. À cet effet, 8 refuges notés A, B, C, D, E, F, G et H
ont été sélectionnés.
Le deuxième graphe \(\mathcal{G}'\) de la partie 1 permet de visualiser les différents
itinéraires possibles, les sommets représentant les refuges et les arêtes
schématisant tous les sentiers de randonnée balisés les reliant.
On donnera la réponse sous la forme d'une suite de sommets espacés par des tirets. Par exemple : A-B-C-D.
Le graphe \(\mathcal{G}'\) est complété ci-dessous par la longueur en
kilomètres de chacun des sentiers.
Pour plus de clarté, la matrice des distances de ce graphe est également fournie : \[M_{d}=\begin{pmatrix}0 & 6 & 3 & 0 & 3 & 9 & 7 & 1\\6 & 0 & 0 & 0 & 0 & 9 & 0 & 0\\3 & 0 & 0 & 0 & 0 & 0 & 0 & 9\\0 & 0 & 0 & 0 & 0 & 3 & 0 & 7\\3 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\9 & 9 & 0 & 3 & 0 & 0 & 1 & 0\\7 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\1 & 0 & 9 & 7 & 1 & 0 & 0 & 0\end{pmatrix}\]
Le club alpin désire aussi proposer à ses membres l'itinéraire le plus court reliant H à G.
On donnera la réponse sous la forme d'une suite de sommets espacés par des tirets. Par exemple : A-B-C-D.
Exercice 3 : Distance entre deux sommets d'un graphe orienté.
On considère le graphe orienté ci-dessous.
Déterminer la distance du sommet \(G\) au sommet \(C\).
Exercice 4 : Donner la matrice d'adjacence d'un graphe orienté et son diamètre.
On considère le graphe orienté ci-dessous.
Donner la matrice d'adjacence ligne-colonne de ce graphe en ordonnant les sommets par ordre alphabétique.
Déterminer son diamètre.
Exercice 5 : Déterminer depuis une matrice si le graphe associé est orienté.
Parmi les matrices suivantes, sélectionner celles dont le graphe associé est orienté.
- 1.\(\begin{pmatrix}0 & 0 & 1 & 0 & 0\\0 & 0 & 0 & 1 & 1\\1 & 1 & 0 & 0 & 0\\1 & 0 & 0 & 0 & 1\\0 & 1 & 1 & 1 & 0\end{pmatrix}\)
- 2.\(\begin{pmatrix}0 & 0 & 1 & 0 & 0\\0 & 0 & 0 & 1 & 0\\1 & 0 & 0 & 1 & 1\\0 & 1 & 1 & 0 & 0\\0 & 0 & 1 & 0 & 0\end{pmatrix}\)
- 3.\(\begin{pmatrix}0 & 1 & 1 & 1 & 0\\1 & 0 & 0 & 1 & 0\\1 & 0 & 0 & 1 & 0\\1 & 1 & 1 & 0 & 1\\0 & 0 & 0 & 1 & 0\end{pmatrix}\)
- 4.\(\begin{pmatrix}0 & 0 & 1 & 0 & 0\\0 & 0 & 0 & 0 & 0\\1 & 1 & 0 & 0 & 1\\1 & 0 & 1 & 0 & 1\\0 & 0 & 1 & 0 & 0\end{pmatrix}\)