THE MATHS TAILOR

Graphes | The Maths Tailor

Graphes

Cours Exercices

Cours

1Le vocabulaire des graphes

2Matrice d'adjacence associée à un graphe

Contenu réservé aux abonnés

3Graphes orientés et graphes pondérés

Contenu réservé aux abonnés

4Chaîne de Markov

Contenu réservé aux abonnés

5Distribution invariante d'une chaîne de Markov

Contenu réservé aux abonnés

Méthodes10

ClassiqueIdentifier le vocabulaire et les caractéristiques d'un graphe

Objectif : lire un graphe (schéma ou liste d'arêtes) et en extraire les caractéristiques demandées.

Méthode

1. Ordre du graphe : compter le nombre de sommets.
2. Degré d'un sommet : compter le nombre d'arêtes qui en partent (une boucle compte pour 2).
3. Adjacence : deux sommets sont adjacents s'ils sont reliés par une arête.
4. Sous-graphe : graphe obtenu en supprimant certains sommets (et les arêtes qui leur sont associées) ou certaines arêtes du graphe initial.
5. Nature du graphe :
- orienté si les arêtes ont un sens de parcours (on parle alors d'arcs) ; non orienté sinon ;
- simple s'il ne possède ni boucle, ni arête multiple entre deux mêmes sommets ;
- complet si deux sommets quelconques sont toujours adjacents ;
- connexe si deux sommets quelconques sont toujours reliés par une chaîne.

Point de vigilance : un graphe complet d'ordre $n$ possède $\frac{n ( n - 1 )}{2}$ arêtes (chaque sommet est relié aux $n - 1$ autres, et chaque arête est comptée deux fois).

TunnelUtiliser la propriété de la somme des degrés d'un graphe

Méthode complète avec le plan Élève

Voir les offres

TunnelDémontrer qu'un graphe est connexe à l'aide des puissances de la matrice d'adjacence

Méthode complète avec le plan Élève

Voir les offres

TunnelProuver qu'un nombre de groupes ne suffit pas par un sous-graphe complet ou un cycle

Méthode complète avec le plan Élève

Voir les offres

TunnelDéterminer si un graphe admet une chaîne ou un cycle eulérien

Méthode complète avec le plan Élève

Voir les offres

ClassiqueTrouver une chaîne ou un cycle eulérien par l'algorithme de Fleury

Méthode complète avec le plan Élève

Voir les offres

ClassiqueConstruire la matrice d'adjacence d'un graphe orienté ou non orienté

Méthode complète avec le plan Élève

Voir les offres

PavlovRetrouver le degré d'un sommet à partir de la matrice d'adjacence

Méthode complète avec le plan Élève

Voir les offres

TunnelÉtudier l'évolution d'un graphe probabiliste (chaîne de Markov)

Méthode complète avec le plan Élève

Voir les offres

ClassiqueDéterminer l'état stable d'une chaîne de Markov

Méthode complète avec le plan Élève

Voir les offres

Exercices

Ordre et degrés des sommets d'un graphe non orienté

On considère un graphe simple non orienté d'ordre 5 dont les sommets sont notés

A, B, C, D, E

.
Les arêtes de ce graphe sont

A B, A C, B C, C D

et

D E

.
1. Déterminer le degré de chacun des sommets de ce graphe.
2. Ce graphe est-il complet ? Justifier la réponse.

Connexité d'un réseau et recherche d'une chaîne

Un réseau de distribution électrique relie six postes de transformation notés

A, B, C, D, E, F

.
Les lignes électriques directes existantes sont

A B, B C, C D, D A

d'une part, et

E F

d'autre part.
1. Le graphe non orienté représentant ce réseau est-il connexe ? Justifier rigoureusement.
2. On installe une nouvelle ligne électrique reliant les postes

C

et

E

. Le graphe devient-il connexe ? Si oui, donner une chaîne reliant le poste

A

au poste

F

et préciser sa longueur.

Analyse structurelle d'un réseau ferroviaire régional

Un réseau ferroviaire régional relie cinq gares notées

A

,

B

,

C

,

D

et

E

. Les liaisons directes bidirectionnelles entre ces gares sont modélisées par les arêtes d'un graphe non orienté

G

:

{A, B}

,

{A, C}

,

{B, C}

,

{B, D}

,

{C, D}

,

{C, E}

et

{D, E}

.
1. Déterminer l'ordre du graphe

G

ainsi que le degré de chacun de ses sommets.
2. Ce graphe est-il simple ? Justifier.
3. Ce graphe est-il complet ? Justifier la réponse.

Déterminer l'ordre du graphe $G$ ainsi que le degré de chacun de ses sommets.
Ce graphe est-il simple ? Justifier.
Ce graphe est-il complet ? Justifier la réponse.

Ordre, sommets isolés et somme des degrés

On considère un réseau de surveillance environnementale modélisé par un graphe simple non orienté

G

comportant 6 stations notées

A, B, C, D, E

et

F

.
Les liaisons de communication existantes entre ces stations sont données par les arêtes suivantes :

A B, B C, C D, D E, E A

et

A C

.
1. Quel est l'ordre du graphe

G

?
2. Déterminer le degré de chacun des sommets de

G

.
3. Vérifier la formule

S \sum de g (S) = 2 m

en la comparant au nombre total d'arêtes

m

du graphe

G

.
4. Le graphe

G

est-il connexe ? Est-il complet ? Justifier chaque réponse.

Quel est l'ordre du graphe $G$ ?
Déterminer le degré de chacun des sommets de $G$ .
Vérifier la formule $S \sum de g (S) = 2 m$ en la comparant au nombre total d'arêtes $m$ du graphe $G$ .
Le graphe $G$ est-il connexe ? Est-il complet ? Justifier chaque réponse.

Étude de connexité et distance dans un réseau de passerelles

Un complexe de recherche est composé de 5 laboratoires désignés par les lettres

A, B, C, D

et

E

.
Des passerelles piétonnes directes permettent de circuler dans les deux sens entre certains laboratoires. Le graphe

G

associé a pour arêtes :

A B, B C, C D, B E

et

D E

.
1. Démontrer que le graphe

G

est connexe.
2. Énumérer toutes les chaînes reliant le sommet

A

au sommet

D

sans passer deux fois par le même sommet (chaînes simples).
3. Déterminer la longueur de chacune de ces chaînes simples et préciser la distance entre

A

et

D

dans le graphe.

Démontrer que le graphe $G$ est connexe.
Énumérer toutes les chaînes reliant le sommet $A$ au sommet $D$ sans passer deux fois par le même sommet (chaînes simples).
Déterminer la longueur de chacune de ces chaînes simples et préciser la distance entre $A$ et $D$ dans le graphe.

Trajectoire probabiliste d'un drone de surveillance sur trois secteurs

Un drone de surveillance patrouille au-dessus d'un complexe sécurisé divisé en trois zones notées

Z_{1}

,

Z_{2}

et

Z_{3}

. Les déplacements d'une ronde à la suivante sont régis par la matrice de transition :

M = 0 0, 5 0, 3 0, 6 0 0, 7 0, 4 0, 5 0

À l'instant initial

t = 0

, le drone se trouve avec certitude dans la zone

Z_{1}

.
1. Donner la matrice ligne

π_{0}

représentant la distribution initiale dans l'ordre

(Z_{1}, Z_{2}, Z_{3})

.
2. Déterminer la matrice ligne

π_{1}

donnant la probabilité de présence du drone dans chaque zone à l'étape

t = 1

.
3. Calculer la distribution de probabilité

π_{2}

à l'étape

t = 2

et vérifier la cohérence du résultat.

Donner la matrice ligne $π_{0}$ représentant la distribution initiale dans l'ordre $(Z_{1}, Z_{2}, Z_{3})$ .
Déterminer la matrice ligne $π_{1}$ donnant la probabilité de présence du drone dans chaque zone à l'étape $t = 1$ .
Calculer la distribution de probabilité $π_{2}$ à l'étape $t = 2$ et vérifier la cohérence du résultat.