[PDF] [PDF] Théorie des graphes Le programme Python suivant permet

View - Download [PDF] Théorie des graphes

Previous PDF

Next PDF

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 1/21

Objectifs pédagogiques :

Modéliser des situations sous forme de graphes.

Chercher un chemin dans un graphe

de la théorie des graphes et de la recherche opérationnelle sont aujourd'hui immenses tant au plan civil que militaire :

aide à la prise de décision ; recherche de la meilleure stratégie ;

La théorie des graphes n'est pas une branche indépendante des mathématiques, elle se rattache à la programmation

linéaire, la programmation convexe (où le concept plus général de fonction convexe remplace les fonctions linéaires

et affines), la topologie, le calcul des probabilités.

1. Un peu de vocabulaire sur les graphes

certains étant reliés par des segments de droites ou de courbes (simples) appelés arêtes, la disposition des sommets

et la forme choisie pour les arêtes n'intervenant pas. Le nombre de sommets du graphe est son ordre. Sauf indication

contraire, un graphe sera considéré comme non orienté et les arêtes pourront être parcourues dans les deux sens. Ce

type de graphe peut se présenter dans des problèmes élémentaires de type combinatoire. La plupart des applications

de la théorie graphes, (problèmes d'optimisation, communications, trafics aériens, ...) conduisent à des graphes

orientés où les arêtes orientées sont appelées arcs. Le degré d'un sommet est le nombre d'arêtes auxquelles il est

relié. Deux sommets d'un graphe sont dits adjacents s'il existe une arête (ou un arc) qui les relie. Un graphe est

dit complet si deux quelconques de ses sommets sont adjacents

Graphe non orienté

Graphe orienté

S1 S2 S3 S1 S2 S3

Sommet

Sommet

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 2/21 en outre complets.

2. Le dilemme du gardien de parc

Situation réelle

Situation modélisée par un graphe non orienté

Vous travaillez dans un parc et devez entretenir les ponts représentés en rouge sur la figure ci-dessus. Pour économiser

du temps et de l'énergie, vous désirez passer sur chaque pont une et une seule fois. Q1. Etablir le graphe modélisant la situation décrite. Q2. En partant de la zone C, trouvez tous les chemins possibles. Q3. Cela est-il possible en commençant depuis l'île B ? Expliquez. Q5. Précisez le degré de chaque sommet du graphe.

Q6. Pourquoi, selon vous, le graphe modélisant le situation étudiée est-il qualifié de non orienté.

Précurseur avec Leibniz de la théorie des graphes et de la topologie, Euler résolut (1735) le problème des sept ponts

Situation réelle

Situation modélisée par un graphe non orienté A B C D A B C D A B C D A B C D ?

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 3/21

revenir à son point de départ. En représentant le problème par un graphe, on peut alors reformuler la question de la

départ ?

Les deux contraintes importantes sont :

un cycle.

de trouver une condition très simple pour savoir si un tel chemin existe. Euler a remarqué ceci :

il faut donc que chaque quartier comporte un nombre pair de ponts. Q7. Etablir le graphe modélisant la situation décrite. Q8. Le problème des 7 ponts admet-il une solution ? Justifier.

4. Réseaux sociaux : modélisation par un graphe

Au premier trimestre 2020, Facebook© revendiquait 2,6 milliards d'utilisateurs actifs chaque mois, en hausse de 9,2% par

rapport à début 2019. Le réseau social américain a passé la barre symbolique des 2 milliards au deuxième trimestre 2017. A

noter que 42% des utilisateurs actifs mensuels de Facebook viennent d'Asie-Pacifique, 15,6% sont Européens et 9,7% sont

4.1. Principe de la modélisation par un graphe non orienté

Imaginez un réseau social ayant 7 abonnés (L, M, N, O, P, Q et R) où :

L est ami avec M, N, O et P ;

M est ami avec L et P ;

N est ami avec L, O et P ;

O est ami avec L,N,P,Q et R ;

P est ami avec O,L et M ;

Q est ami avec N et O ;

R est ami avec O.

La description de ce réseau social, malgré son faible nombre d'abonnés, est déjà quelque peu compliquée, alors imaginez cette même description avec un réseau social comportant des millions d'entre eux ! Il existe un moyen plus "visuel" pour représenter ce réseau social : on peut représenter chaque abonné par un cercle (avec le nom de l'abonné situé dans le cercle) et chaque relation "X est ami avec Y" par un segment de droite reliant X et Y ("X est ami avec Y" et "Y est ami avec X" étant représenté par le même segment de droite). Le mini-réseau social décrit précédemment peut être modélisé sous la forme du graphe ci-contre.

Modélisation du mini-réseau social sous

Arête

Sommet

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 4/21

>>> La distance entre deux sommets d'un graphe est le nombre minimum d'arêtes pour aller du sommet à un autre.

Exemple : entre L et R la distance est 2.

>>> L'écartement d'un sommet est la distance maximale existant entre ce sommet et les autres sommets du graphe.

Exemple : pour le sommet Q, la plus grande distance avec un autre sommet est 3 ; l'écartement est donc de 3.

>>> Le centre d'un graphe est le sommet d'écartement minimal (le centre n'est pas nécessairement unique).

Exemple : les sommets Q et R ont un écartement de 3, les autres un écartement de 2 ; les centres sont donc L, N, O,

P. >>> Le rayon d'un graphe est l'écartement d'un centre du graphe. Exemple : les centres L, N, O, P ont un écartement de 2 ; le rayon du graphe est donc 2. >>> Le diamètre d'un graphe est la distance maximale entre deux sommets du graphe. Q9. Construisez un graphe de réseau social à partir des informations suivantes :

A est ami avec B, D et E ;

B est ami avec A, C et D ;

C est ami avec B et D ;

D est ami avec A, B, C et E ;

E est ami avec A et F ;

F est ami avec E.

Q10. Compléter le tableau ci-dessous des distances entre sommets :

Distances A B C D E F

A 0 B 0 C 0

D 0

E 0

F 0

Q11. Quel est le centre du graphe

Q12. Quel est le rayon du graphe ?

Q13. Quel est le diamètre du graphe ?

4.2. Implémentation d'un graphe non orienté à l'aide d'une matrice d'adjacence

programme Python. Une matrice est un tableau à double entrée :

Comment construire une matrice d'adjacence ?

Il faut savoir qu'à chaque ligne correspond un sommet du graphe et qu'à chaque colonne correspond aussi un sommet

du graphe. À chaque intersection ligne i-colonne j (ligne i correspond au sommet i et colonne j correspond au sommet

j), on place un 1 s'il existe une arête entre le sommet i et le sommet j, et un zéro s'il n'existe pas d'arête entre le

sommet i et le sommet j.

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 5/21 / colonne, de répondre à la question : Est-ce que le sommet " X » est relié directement au sommet " Y » par une arête ?

Si la réponse est OUI 1

Si la réponse est NON 0

Remarques :

et de colonnes. associée sont symétrique par rapport à la grande diagonale des 0. traduisant la relation " est ami avec »

Graphe non orienté traduisant la relation :

" X est ami avec Y ».

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 6/21

4.3. Implémentation d'un graphe orienté à l'aide d'une matrice d'adjacence

arcs) afin de traduire la relation " X » suit " Y ».

Graphe orienté de traduisant la relation :

" X suit Y »

Remarque ; Zoé est la star du réseau social car elle ne suit personne mais tout le monde la suit.

Q17. Comment peut-on obtenir facilement le nombre de personnes suivies par une personne donnée ? Q18. Comment peut-on obtenir facilement le nombre de personnes qui suivent une personne donnée ?

2 liens entrants (1 depuis la page et 1 depuis la page ).

graphe orienté

Modélisation des liens sortants par liste

Ecriture simplifiée :

Page Lien sortant

Pages : 0 1 2 3 (indices)

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 7/21

Le programme Python suivant permet de simuler le parcours aléatoire du graphe précédent en utilisant une liste

aléatoire comportant nbEtapes :

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 8/21 Remarque : on affichera pas les pages visitées au fur et à mesure du parcours du graphe.

Q23. Les résultats précédents sont-ils sensiblement modifiés si on déplace le lien rouge dans le réseau de pages web

précédent comme figuré ci-dessous ?

de recherche Google. En première approximation un " page rank » simplifié se rapproche des scores de fréquentation

inventé par Larry Page, cofondateur de Google. Ce mot est une marque déposée. Comprendre en vidéo le PR de Google avec PageRank Simulator : https://youtu.be/xdE-L-A2TLA PageRank Simulator : http://faculty.chemeketa.edu/ascholer/cs160/WebApps/PageRank/

La toute première " formule magique » de calcul du PR par Google (la toute dernière est secrète) :

Comment calculer un PS simplifié ? : http://www.canyouseome.com/comment-calculer-le-page-rank/

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 9/21

6. Comment parcourir un graphe ?

représentent les pages du site et les arêtes représentent les liens hypertextes (ou hyperliens) permettant d'aller

d'une page à une autre.

Dans tout ce qui suit, on supposera que ce graphe est connexe, c'est-à-dire qu'à partir d'une page donnée, toute

autre page est accessible par une série de liens (une chaîne). parcourir ce graphe en passant par tous ses sommets.

6.1. Parcours en largeur : Breadth First Search (BFS)

Comment ça marche ?

de ses voisins avant d'explorer leurs enfants. Autrement dit, on commence d'abord par aller sur la plus grande largeur

possible. Son implémentation repose sur une file (queue) dont le principe du premier entré, premier sorti (FIFO : First

d

Remarque : on donne le nom de parcours en largeur d'un graphe car cet algorithme va visiter tous les sommets à

distance 1 du sommet de départ puis tous les sommets à distance 2 du sommet de départ puis tous les sommets à

distance 3 du sommet de départ etc... distance = 0 distance = 1 distance = 2 distance = 3

Exploration

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 10/21

Ressources à consulter :

https://youtu.be/NrQGxfFMYzs

On va procéder à un parcours en largeur du graphe en mettant les sommets successifs dans une file (structure

FIFO). Voici la description intuitive de l'algorithme :

1. On enfile le sommet de départ (on visite la page d'accueil du site).

2. On enfile les sommets adjacents à la tête de file (on visite les pages ciblées par la page d'accueil) s'ils ne sont

pas déjà présents dans la file.

3. On défile (c'est-à-dire on supprime la tête de file).

4. Tant que la file n'est pas vide, on ré-itère les points 2 et 3.

En d'autres termes, on défile toujours prioritairement les sommets (les pages) les plus tôt découverts.

Programmation en Python :

Nous avons vu précédemment la notion de graphe et le fait que tout graphe pouvait être caractérisé par sa matrice

d'adjacence composée de 1 et de 0 selon que deux sommets sont ou ne sont pas reliés par une arête.

Une nouvelle façon d'encoder un graphe sous Python est d'utiliser un dictionnaire qui sera la représentation de sa

matrice d'adjacence. La clé associée à chaque sommet sera la liste des sommets adjacents :

Q24. Montrer, en partant du point B, que la méthode de parcours en largeur (BFS) du graphe précédent se ramène à

un arbre dont le sommet est b. On représentera en pointillés les arêtes entre deux sommets déjà explorés.

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 11/21

réalisera avec une fonction bfs(graphe, sommet_de_depart) dont les variables seront les suivantes :

Un dictionnaire P tel que, en fin de parcours, pour tout sommet S du graphe, P[S] sera le père de S, c'est-à-

dire le sommet à partir duquel le sommet S a été découvert lors du parcours.

Un dictionnaire couleur[] tel que, pour tout sommet S, couleur[S] soit blanc si le sommet S n'est pas passé

dans la file, gris si le sommet S est dans la file et noir si le sommet S est sorti de la file.

Une liste Q utilisée comme file (FIFO) : on enfile un sommet lorsqu'il est découvert et on le défile lorsqu'il est

terminé (traitement prioritaire des sommets découverts au plus tôt).

Q25. Assurez-vous que le résultat obtenu est conforme à celui obtenu à la main à la question Q24.

Q26. Tester le parcours du graphe en largeur depuis différents sommets et comparer le résultat obtenu avec la

méthode manuelle.

Il est également possible de coder le programme en faisant intervenir la notion de classe comme dans le programme

ci-après.

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 12/21

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 13/21

6.2. Parcours en profondeur : Depth First Search (DFS)

Comment ça marche ?

chaque branche complètement avant de passer à la suivante. Autrement dit, on commence d'abord par aller le plus

Ressources à consulter :

https://youtu.be/kcedjJOjDpg

On va procéder à un parcours en profondeur du graphe en mettant les sommets successifs dans une pile (structure

LIFO). Voici la description intuitive de l'algorithme :

1. On empile le sommet de départ (on visite la page d'accueil du site).

2.

Si le sommet de la pile possède des voisins qui ne sont pas dans la pile, ni déjà passés dans la

pile, alors on sélectionne l'un de ces voisins et on l'empile (en le marquant de son numéro de découverte) Sinon on dépile (c'est-à-dire on supprime l'élément au sommet de la pile).

3. On recommence au point 2 tant que la pile n'est pas vide.

En d'autres termes, on traite toujours en priorité les liens des pages les plus tard découvertes.

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 14/21

Programmation en Python :

Q27. Montrer, en partant du point g, que la méthode de parcours en profondeur (DFS) du graphe précédent se ramène

à un arbre dont le sommet est g. On représentera en pointillés les arêtes entre deux sommets déjà explorés.

programmation du parcours en profondeur (DFS) se réalisera avec une fonction dfs(graphe, sommet_de_depart) dont les variables seront les suivantes :

Un dictionnaire P tel que, en fin de parcours, pour tout sommet S du graphe, P[S] sera le père de S, c'est-à-

dire le sommet à partir duquel le sommet S a été découvert lors que parcours.

Un dictionnaire couleur[] tel que, pour tout sommet S, couleur[S] soit blanc si le sommet S n'est pas passé

dans la file, gris si le sommet S est dans la file et noir si le sommet S est sorti de la file.

Une liste Q utilisée comme pile (LIFO).

Q28. Tester le parcours du graphe en largeur depuis différents sommets et comparer le résultat obtenu avec la

méthode manuelle.

Il est également possible de coder le programme en faisant intervenir la notion de classe comme dans le programme

ci-après.

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 15/21

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 16/21

7. Comment détecter un cycle dans un graphe ?

7.1. Notion de cycle

Un cycle est un sous graphe dont les sommets peuvent être organisés en une séquence fermée.

Graphe orienté :

Graphe non orienté :

tester les programmes des paragraphes suivants.

7.2. Parcours en largeur (BFS)

7.2.1. Graphe orienté

L'idée est très simple, pour vérifier s'il existe un cycle, il suffit de vérifier s'il existe un chemin partant d'un sommet

disons "v" et revenant à ce sommet pour tous les sommets. S'il existe un tel chemin, nous disons que le graphe

contient un cycle. Maintenant, la question est de savoir comment vérifier un tel chemin ? Là encore réponse à cette

question est très simple, exécutez une traversée à partir d'un sommet "v" si nous revenons à ce sommet, nous

retournons True sinon retournons False.

La fonction suivante vérifie s'il existe un chemin partant d'un sommet " u » vers un sommet " v » :

1 5 2 3 4 3 4 5 1 5 2 3 4 3 4 5 Cycle Cycle

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 17/21

La fonction ci-dessus est la fonction principale, maintenant pour vérifier s'il existe un cycle, il suffit de vérifier tous les

sommets s'il existe un chemin partant de ce sommet et y retournant : 1 5 2 3 4

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 18/21

7.2.1. Graphe non orienté

Pour un graphe non orienté, nous appliquons simplement le parcours en largeur pour détecter un cycle. L'idée est

d'utiliser un tableau pour mémoriser le parent de chaque sommet (De quel sommet nous avons découvert chaque

sommet). En découvrant les sommets, on vérifie si on retourne au sommet déjà visité et que ce sommet n'est pas le

parent du sommet courant, si c'est le cas, alors il existe un cycle. 1 5 2 3 4

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 19/21

7.3. Parcours en profondeur (DFS)

7.3.1. Graphe orienté

L'utilisation de la parcours en profondeur est un peu plus compliquée, car l'algorithme est récursif, et comme vous le

savez, derrière chaque algorithme récursif, il existe une pile utilisée pour les appels récursifs. Parce que pendant

l'exécution de l'algorithme, nous n'avons pas accès à cette pile, nous allons devoir créer une pile et suivre les sommets

déjà dans la pile. Comment cette pile est utile pour détecter un cycle ? Pour bien comprendre ce qui se passe, on

sont empilés vers la pile et dépilés :

Revenons maintenant à la question de savoir comment il est utile de savoir quel élément est déjà dans la pile

Lors de l'exécution de l'algorithme, si nous revenons à un élément " i » (Visités[i] = True) qui existe déjà dans la pile

(Pile[i] = True), (Visités[i] = True) et on ajoute également à la pile (Pile[i] = True sommets adjacents, on le supprime de la pile (Pile[i] = False)

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 20/21 1 5 2 3 4

LGT Saint-Exupéry, Mantes-la-Jolie

Activité Terminale NSI ʹ Théorie des graphes 21/21

7.3.2. Graphe non orienté

La revient à un sommet, que ce sommet n'est pas le parent du sommet de l'appelant. 1 5 2 3 4quotesdbs_dbs44.pdfusesText_44

[PDF] parcours en largeur graphe

[PDF] parcours en profondeur itératif

[PDF] algorithme parcours en profondeur python

[PDF] parcours en largeur graphe java

[PDF] conflit de puissance définition

[PDF] parcours lecture acces pas cher

[PDF] parcours lecture pdf

[PDF] parcours lecture le petit chaperon rouge

[PDF] parcours lecture acces avis

[PDF] parcours lecture occasion

[PDF] coexistence pacifique cours

[PDF] archives militaire en ligne

[PDF] livret militaire en ligne

[PDF] la coexistence pacifique de 1953 ? 1962 pdf

[PDF] cornière catnic