Graphe exercice BAC 2013 (réf 1678) Chapitre 5 graphes et chaînes de Markov, Option maths expertes, séquence 5 exercices de synthèse et devoirs d'entraînement

Dans le graphe ci-dessous, les sommets représentent différentes zones de résidence ou d'activités d'une municipalité.
Une arête reliant deux de ces sommets indique l'existence d'une voie d'accès principale entre deux lieux correspondants.
matrice d'un graphe

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

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

Infos abonnements

Ressource précédente: graphe et algorithme de dijkstra (réf 1677) Ressource suivante: graphe probabiliste et algorithme de dijkstra (bac 2014) (réf 1680)