Envoyez votre messageInfos
Vous devez être inscrit pour accéder à ces informations.
Ceci vous permet de visualiser les ressources déjà vues et marquer à revoir celles qui nécessitent d'être retravaillées.
Contenu
Matrice d’un graphe
Chemins de longueur 4 sur un graphe
Existence d’une chaîne ou d’un cycle eulérien
Algorithme de Dijkstra
Ressources associées et exercices semblables
graphe probabiliste et algorithme de dijkstra (bac 2014) (réf 1680)
exercice
graphe probabiliste et algorithme de dijkstra (ex bac 2013) (réf 1681)
exercice
On appelle H le hall d'entrée et B le bureau du directeur.
En fin de journée, un agent de service fait le tour de la MJC pour récupérer dans chaque salle (bureau du directeur et hall inclus) les objets oubliés par les enfants.
- Préciser si ce graphe est connexe en justifiant la réponse.
Rappel cours
Graphe connexe
Un graphe connexe est un graphe non orienté dans lequel il existe un chemin entre chaque paire de sommets.Aide
Il faut trouver une chaîne passant par tous les sommets
Solution
Vous devez être inscrit pour accéder à ce contenu gratuitement!
INSCRIPTION - Déterminer, en justifiant, si l'agent de service peut passer par toutes les salles en utilisant une fois et une seule chaque passage.
Rappel cours
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érien
Un cycle eulérien 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 déterminer s'il existe une chaîne eulérienne ou des cycles eulériens.
Solution
Vous devez être inscrit pour accéder à ce contenu gratuitement!
INSCRIPTION - On range les 7 sommets par ordre alphabétique.
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 iième ligne et de la jiè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 inscrit pour accéder à ce contenu gratuitement!
INSCRIPTION - On donne:
$M^4 = \begin{pmatrix} 31 &15 &26 &21 &27 &18 &12\\ 15 &12 &15 &12 &18 &12 &6\\ 26 &15 &31 &18 &27 &21 &12\\ 21 &12 &18 &20 &17 &18 &5\\ 27 &18 &27 &17 &34 &17 &16\\ 18 &12 &21 &18 &17 &20 &5\\ 12 &6 &12 &5 &16 &5 &10\\ \end{pmatrix}$
En déduire le nombre de chemins de longueur 4 entre les sommets B et H.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$.}Solution
Vous devez être inscrit pour accéder à ce contenu gratuitement!
INSCRIPTION - On a indiqué sur le graphe ci-dessous le temps en minute mis pour passer entre les différentes salles en ouvrant et fermant les portes à clé.
À l'aide de l'algorithme de Dijkstra, on va déterminer le temps minimal pour aller de B à H.
Solution
Vous devez être inscrit pour accéder à ce contenu gratuitement!
INSCRIPTION