1 GRAPHES (Partie 2) I. Graphes orientés et graphes pondérés 1 ...

GRAPHES (Partie 2)
I. Graphes orientés et graphes pondérés 1) Graphes orientés Définitions : - Un graphe est orienté si ses arêtes, appelées arcs dans ce
cas, ont un sens de parcours.
- Un chemin est une succession d'arcs mis bout à bout.
- Un circuit est un chemin fermé dont les arcs sont tous distincts. Exemple :
Le graphe orienté ci-contre est d'ordre 3 car il possède 3 sommets.
Il possède une boucle sur le sommet A.
A - C - B est un chemin de longueur 2.
B - C - B - A - A - C - B est un chemin fermé de longueur 6.
A - C - B - A est un circuit de longueur 3. 2) Graphes pondérés Définitions : - Un graphe est étiqueté si ses arêtes (ou ses arcs) sont
affectés d'étiquettes (mots, lettres, symboles, nombres, ...)
- Dans le cas où les étiquettes sont des nombres, le graphe est dit
pondéré. Les étiquettes sont appelées les poids entre les sommets.
- Le poids du chaîne (respectivement d'un chemin) est la somme des poids
des arêtes (respectivement des arcs) constituant la chaîne (respectivement
le chemin). Exemple :
Le graphe orienté ci-contre est pondéré.
Le poids entre le sommet B et le sommet A est égal à 5.
Le poids du chemin B - C - B - A est égal à :
1 + 3 + 5 = 9 [pic] Vidéo https://youtu.be/ZEiOWcqX7S4 Remarque :
Le chemin le plus court entre deux sommets est le chemin qui a le poids
minimum. 3) Matrice associée à un graphe orienté Définition : Soit un graphe G orienté d'ordre n dont les sommets sont
numérotés de 1
à n.
La matrice d'adjacence associée à G est la matrice carrée de taille n dont
chaque terme [pic] est égal au nombre d'arcs orientés reliant les sommets i
et j.
Exemple : [pic] Vidéo https://youtu.be/yRBCx3uxN9A La matrice d'adjacence associée au graphe ci-contre est :
[pic]
Méthode : Trouver le plus court chemin dans un graphe en utilisant
l'algorithme de Dijkstra [pic] Vidéo https://youtu.be/rHylCtXtdNs Le graphe ci-contre représente un réseau routier entre 7 villages A, B, C,
D, E, F et G. Les étiquettes correspondent aux distances en kilomètres
séparant deux villages.
On veut déterminer le chemin le plus court entre les villages A et G. Il s'agit donc de déterminer le chemin reliant A et G dont le poids est
minimum.
On va utiliser l'algorithme de Dijkstra : A |B |C |D |E |F |G |Légende : | |0 |1 - A |2 - A | | | | |(1) | | |1 - A |
|3 - B | |4 - B | |(2) | | | |2 - A |5 - C |6 - C | | |(3) | | | | |3 - B
|5 - D |6 - D |6 - D |(4) | | | | | | |4 - B |8 - F |(5) | | | | | |5 - D |
|10 - E |(6) | | | | | | | |6 - D |(7) | |
Explications :
On complète le tableau dans l'ordre de la ligne (1) à la ligne (7) : (1) : On part de A avec 0 km.
On ne reviendra plus en A, donc on colorie en bleu toute la colonne A.
Partant de A, pour aller en B, on a parcouru 1 km : d'où le notation "1 -
A".
Partant de A, pour aller en C, on a parcouru 2 km : d'où la notation "2 -
A". (2) : On choisit le sommet B qui a la plus petite distance (1).
On ne reviendra plus en B, donc on colorie toute la colonne B.
Partant de B, pour aller en D, on a parcouru 1+2 = 3 km.
Partant de B, pour aller en F, on a parcouru 1+3 = 4 km. (3) : On choisit le sommet C qui a la plus petite distance (2).
On ne reviendra plus en C, donc on colorie toute la colonne C.
Partant de C, pour aller en D, on a parcouru 2+3 = 5 km.
Partant de C, pour aller en E, on a parcouru 2+4 = 6 km. (4) : On choisit le sommet D qui a la plus petite distance (3 en 2e ligne).
On ne reviendra plus en D, donc on colorie toute la colonne D.
Partant de D, pour aller en E, on a parcouru 3+2 = 5 km.
Partant de D, pour aller en F, on a parcouru 3+3 = 6 km.
Partant de D, pour aller en G, on a parcouru 3+3 = 6 km. (5) : On choisit le sommet F qui a la plus petite distance (4 en 2e ligne).
On ne reviendra plus en F, donc on colorie toute la colonne F.
Partant de F, pour aller en G, on a parcouru 4+4 = 8 km. (6) : On choisit le sommet E qui a la plus petite distance (5).
On ne reviendra plus en E, donc on colorie toute la colonne E.
Partant de E, pour aller en G, on a parcouru 5+5 = 10 km. (7) : On choisit le sommet G qui a la plus petite distance (6). Le chemin le plus court est donc égal à 6 km.
Pour obtenir ce chemin, on suit "à l'envers" les correspondances du tableau
:
Colonne G : 6 - D
Colonne D : 3 - B
Colonne B : 1 - A
Colonne A : 0
Le chemin le plus court est donc A - B - D - G. II. Graphes probabilistes 1) Définition Dans une équipe de football, on étudie les passes que se font trois
attaquants A, B et C.
Les probabilités qu'un attaquant passe le ballon à un autre sont
schématisées sur le graphe orienté et pondéré suivant. Chaque passe de
ballon correspond à une nouvelle expérience aléatoire dont les issues sont
A, B ou C (un des trois attaquants est susceptible de recevoir le ballon). Par exemple, la probabilité que l'attaquant A passe le ballon à l'attaquant
B est égale à [pic]. Les poids des arcs sont alors des probabilités. Un tel schéma est appelé un graphe probabiliste. Définition : Un graphe probabiliste est un graphe orienté et pondéré
possédant au plus un arc entre deux sommets et dont la somme des poids des
arcs issus d'un même sommet est égal à 1. Par exemple, la somme des poids issus de A est égal à [pic]. 3) Matrice de transition Définition : Soit G un graphe probabiliste d'ordre n dont les sommets sont
numérotés de 1 à n.
La matrice de transition de G est la matrice carrée d'ordre n dont le
coefficient situé sur la ligne i et la colonne j est la probabilité portée
par l'arc reliant le sommet i vers le sommet j s'il existe et 0 dans le cas
contraire. [pic] Vidéo https://youtu.be/KRi0C_zOsHs Dans l'exemple, la matrice de transition est : [pic] On trouve par exemple à l'intersection de la première ligne et de la
deuxième colonne la probabilité que le ballon arrive chez l'attaquant B
alors qu'il se trouvait chez l'attaquant A.
Remarques :
- Le coefficient [pic] de la matrice M est nul car la probabilité que
l'attaquant A garde le ballon est nulle. Il en est de même pour les
coefficients [pic] et [pic].
- La somme des coefficients d'une même ligne d'une matrice de transition
est égale à 1.
Définition : L'état probabiliste après n étapes est la matrice ligne dont
les coefficients sont les probabilités d'arrivée en chaque sommet après n
étapes.
Exemple :
Dans l'exemple des passeurs au football, l'état probabiliste après 3 étapes
donnerait les probabilités que le ballon se trouve chez l'attaquant A, chez
l'attaquant B et chez l'attaquant C après 3 passes. L'arbre de probabilité ci-contre permet de résumer les probabilités de
l'étape n à l'étape n+1. A l'aide de la formule des probabilités totales, on a : [pic] On note [pic] l'état probabiliste après
n étapes. On a alors : [pic]. Propriété : On considère un graphe probabiliste de matrice de transition M
et dont l'état probabiliste après n étape est [pic].
Pour tout entier naturel n, on a : [pic] et [pic] où P0 est l'état
initial. - Admis - Exemple : [pic] Vidéo https://youtu.be/gxrgpotHfnE Dans l'exemple précédent, on suppose l'attaquant A possède le ballon à
l'étape 0.
La matrice ligne des états après la 3e étape est égale à :[pic].
On a [pic] car le ballon part de A.
Avec la calculatrice, on obtient : [pic]
Donc [pic]. Ainsi par exemple, la probabilité que l'attaquant C possède le ballon après
la 3e passe est égale à [pic].
4) Etat stable Définition : Un état probabiliste est dit stable lorsqu'il n'évolue pas
lors de répétitions de l'expérience. Propriété : Soit un graphe probabiliste d'ordre 2 dont la matrice de
transition ne comporte pas de 0.
L'état stable P vérifie alors l'égalité [pic].
Et si n tend vers l'infini, alors l'état probabiliste Pn tend vers l'état
stable P. - Admis -
Exemple :
On considère le graphe probabiliste ci-contre : Vérifions à l'aide de la calculatrice, que l'état stable est la matrice
ligne [pic].
La matrice de transition est [pic]. L'état stable P vérifie l'équation [pic], en effet : [pic] Méthode : Déterminer un état stable [pic] Vidéo https://youtu.be/PS756B-M0Dw On considère le graphe probabiliste ci-dessous :
[pic]
Déterminer l'état stable pour cette situation. La matrice de transition est [pic].
Pour tout entier naturel n, on a : [pic] où [pic] est la suite des états
probabilistes.
L'état stable [pic] vérifie l'équation [pic], soit [pic].
Ainsi, on a le système [pic]
[pic]
Comme [pic], on a [pic] et donc [pic] et [pic].
L'état stable du graphe est donc [pic].
Cela signifie que quelque soit l'état initial (départ de A ou de B), les
probabilités d'être en A et en B tendent respectivement vers [pic] et
[pic]. -----------------------
Hors du cadre de la classe, aucune reproduction, même partielle, autres que
celles prévues à l'article L 122-5 du code de la propriété intellectuelle,
ne peut être faite de ce site sans l'autorisation expresse de l'auteur.
www.maths-et-tiques.fr/index.php/mentions-legales