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
Degré d’un sommet
Matrice d’un graphe
Nombre de chemins de longueur 3
Chaîne eulérienne
Algorithme de Dijkstra
Ressources associées et exercices semblables
graphe et algorithme de dijkstra (réf 1677)
exercice
Une arête reliant deux de ces sommets indique l'existence d'une voie d'accès principale entre deux lieux correspondants.
- Donner, sans justifier, le degré de chacun des sommets (la réponse pourra être présentée sous forme de tableau où les sommets seront mis dans l'ordre alphabétique).
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 - Donner la matrice $M$ associée au graphe (les sommets seront mis dans l'ordre alphabétique).
Aide
Rappel: $M$ est une matrice carrée d'ordre 7 avec des coefficients 0 et 1
Solution
Vous devez être abonné pour accéder à ce contenu...
Infos abonnements - On donne la matrice $M^3 =\begin{pmatrix}
2 & 7 & 8 & 5 & 5 & 5 & 3 \\
7 & 8 & 12 & 13 & 12 & 8 & 5\\
8 & 12 & 12 &15 & 13 & 13 & 5\\
5 & 13 & 15 & 12 & 13 & 12 & 8\\
5 & 12 & 13 & 13 & 10 & 12 & 5\\
5 & 8 & 13 & 12 & 12 & 8 & 7\\
3 & 5 & 5 & 8 & 5 & 7 & 2\\
\end{pmatrix}$
Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant $A$ et $F$ puis donner leur liste.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 abonné pour accéder à ce contenu...
Infos abonnements - Pour sa campagne électorale, un candidat souhaite parcourir toutes les voies d'accès principales de ce quartier sans emprunter plusieurs fois la même voie.
Montrer qu'un tel parcours est possible.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é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 donc chercher s'il existe des chaînes ou cycles eulériens
Solution
Vous devez être abonné pour accéder à ce contenu...
Infos abonnements - Dans le graphe ci-dessous, les valeurs indiquent, en minutes, les durées moyennes des trajets entre les différents lieux via les transports en commun.
Ce même candidat se trouve à la mairie $(A)$ quand on lui rappelle qu'il a un rendez-vous avec le responsable de l'hôpital situé en zone $G$.
En utilisant l'algorithme de Dijkstra, déterminer le chemin de durée minimale que ce candidat devra emprunter pour arriver à son rendez-vous.Solution
Vous devez être abonné pour accéder à ce contenu...
Infos abonnements