Devoir graphes: vocabulaire, matrice… (réf 1683) Chapitre 5 graphes et chaînes de Markov, Option maths expertes, séquence 5 exercices de synthèse et devoirs d'entraînement

Représenter un graphe complet d'ordre 4.

Rappel cours

Graphe complet
On appelle graphe complet un graphe dont tous les sommets sont adjacents entre eux.

Aide

L'ordre 4 signifie 4 sommets

Solution

Vous devez être abonné pour accéder à ce contenu...
Infos abonnements
On donne la matrice d'un graphe $G$: $\begin{pmatrix} 0&1&1&1&0\\ 0&0&0&1&0\\ 0&0&0&0&0\\ 0&0&0&0&1\\ 0&1&0&0&0\\ \end{pmatrix}$
Quel est l'ordre de ce graphe?
S'agit-il d'un graphe non orienté ou orienté? pourquoi?
Représenter le graphe associé à cette matrice.

Rappel cours

Matrice associée à un graphe
La matrice associée à un graphe d'ordre $n$ dont les sommets sont numérotés de 1 à n est une matrice carrée de dimension $n$, où le terme à l'intersection de la i^ième ligne et de la j^ième colonne est nombre d'arêtes reliant i et j.
Cette matrice est appelée matrice d'adjacence du graphe.

Solution

Vous devez être abonné pour accéder à ce contenu...
Infos abonnements
On donne le graphe ci-dessous:
1. Quel est l'ordre de ce graphe?
  
  Solution
  
  Vous devez être abonné pour accéder à ce contenu...
  Infos abonnements
2. Est-il complet? (justifier)
  
  Rappel cours
  
  Graphe complet
  On appelle graphe complet un graphe dont tous les sommets sont adjacents entre eux.
  
  Solution
  
  Vous devez être abonné pour accéder à ce contenu...
  Infos abonnements
3. Donner le degré de chaque sommet.
  En déduire le nombre d'arêtes(calcul) et contrôler avec le graphe.
  
  Rappel cours
  
  Degré d'un sommet
  Deux sommets reliés par une arête sont adjacents.
  Le degré d'un sommet est le nombre d'arêtes rejoignant ce sommet.
  
  Solution
  
  Vous devez être abonné pour accéder à ce contenu...
  Infos abonnements
4. Donner la matrice d'adjacence de ce graphe.
  
  Rappel cours
  
  Matrice associée à un graphe
  La matrice associée à un graphe d'ordre $n$ dont les sommets sont numérotés de 1 à n est une matrice carrée de dimension $n$, où le terme à l'intersection de la i^ième ligne et de la j^ième colonne est nombre d'arêtes reliant i et j.
  Cette matrice est appelée matrice d'adjacence du graphe.
  
  Solution
  
  Vous devez être abonné pour accéder à ce contenu...
  Infos abonnements
5. Citer une chaîne de longueur 5 reliant le sommet $A$ au sommet $C$
  
  Rappel cours
  
  Chaîne
  Une chaîne est un liste ordonnée de sommets telle que chaque sommet de la liste soit adjacent au suivant.
  La longueur d'une chaîne est le nombre d'arêtes qui la composent.
  Si l'origine et l'extrémité de la chaîne sont identiques alors il s'agit d'une chaîne fermée
  
  Solution
  
  Vous devez être abonné pour accéder à ce contenu...
  Infos abonnements
6. Combien y-a-t'il de chaînes de longueur 3 allant du sommet $B$ au sommet $E$?
  
  Rappel cours
  
  Nombre de chemins de longueur $p$
  Nombre de chaînes de longueur $p$}{Soit $G$ un graphe d'ordre $n$ et de matrice d'adjacence $M$.
  Le coefficient $m_{ij}$ de la matrice $M^p$ ($p$ entier naturel non nul) est le nombre de chaînes de longueur $p$ reliant les sommets $i$ et $j$.}
  
  Aide
  
  Il faut calculer $M^3$
  
  Solution
  
  Vous devez être abonné pour accéder à ce contenu...
  Infos abonnements
7. Combien y-a-t'il de allant du sommet $A$ au sommet $F$ passant par 3 sommets(pas nécessairement distincts)?
  
  Solution
  
  Vous devez être abonné pour accéder à ce contenu...
  Infos abonnements

Bonus Existe-t-il une chaîne passant par une seule fois par toutes les arêtes reliant deux sommets du graphe?(justifier)
Si ce n'est pas possible, combien faut-il ajouter d'arêtes au minimum pour que ce soit possible? la(les) représenter sur le graphe?

Rappel cours

Graphe connexe
Un graphe connexe est un graphe non orienté dans lequel il existe un chemin entre chaque paire de sommets.
Chaîne eulérienne
Une chaîne eulérienne est une chaîne sur le graphe utilisant toutes les arêtes une et une seule fois.
existence d'une chaîne eulérienne
Un graphe connexe admet une chaîne eulérienne si et seulement si ses sommets sont tous de degré pair sauf deux d'entre eux.
Cycle eulérienne
Un cycle eulérienne est une chaîne fermée sur le graphe utilisant toutes es arêtes une et une seule fois.
existence d'un cycle eulérien
Un graphe connexe admet un cycle eulérien si et seulement si ses sommets sont tous de degré pair.

Aide

Il faut chercher s'il existe une chaîne ou un cycle eulérien

Solution

Vous devez être abonné pour accéder à ce contenu...
Infos abonnements

Vous devez être abonné pour accéder à ce contenu...

Infos abonnements

Ressource précédente: chaîne de markov à trois états, algorithme de dijkstra (ex bac 2019) (réf 1682) Ressource suivante: devoir graphes probabilistes à deux ou trois états (réf 1685)