43 lines
2.0 KiB
Markdown
43 lines
2.0 KiB
Markdown
# **Graphes**
|
|
|
|
Construire un graphe non orienté du réseau social à partir des informations suivantes :
|
|
|
|
- **Arthur** est ami avec **Benoit** et **Elodie** ;
|
|
- **Benoit** est ami avec **Arthur** et **Coralie** ;
|
|
- **Coralie** est amie avec **Benoit**, **Franck** et **David** ;
|
|
- **David** est ami avec **Coralie**, **Franck** et **Elodie** ;
|
|
- **Elodie** est ami avec **Arthur**, **David** et **Franck** ;
|
|
- **Franck** est ami avec **Coralie**, **David** et **Elodie**.
|
|
|
|
---
|
|
|
|
Eva décide de faire un graphe orienté représentant les différentes ruelles de son village. On y trouve une boulangerie, une école, un bureau de poste, une boucherie, une mairie, une église et une salle des fêtes. Certaines ruelles sont à double sens et d'autres à sens unique.
|
|
|
|
Eva décide de donner pour chacune des arêtes de son graphe une valeur qui correpond au temps qu'elle met pour traverser la ruelle à pied (chaque arête représente un sens de circulation).
|
|
|
|
Voici ses données :
|
|
|
|
- il y a une ruelle entre la boulangerie et le bureau de poste (double sens) - 2 minutes ;
|
|
- il y a une ruelle entre la boulangerie et l'école (sens unique de l'école vers la boulangerie) - 3 minutes ;
|
|
- il y a une ruelle entre la boulangerie et la boucherie (sens unique de la boulangerie vers la boucherie) - 4 minutes ;
|
|
- il y a une ruelle entre l'école et l'église (sens unique de l'école vers l'église) - 3 minutes ;
|
|
- il y a une ruelle entre l'école et la mairie (sens unique de la mairie vers l'école) - 4 minutes ;
|
|
- il y a une ruelle entre l'école et la salle des fêtes (double sens) - 6 minutes ;
|
|
- il y a une ruelle entre la boucherie et la salle des fêtes (double sens) - 5 minutes ;
|
|
- il y a une ruelle entre la mairie et l'église (double sens) - 7 minutes.
|
|
|
|
**Dessiner le graphe représentant le village d'Eva.**
|
|
|
|
--------
|
|
|
|
**Donner l'ordre du graphe ci dessous ainsi que le degré de chaque sommet.**
|
|
|
|
|
|
|
|
-------
|
|
|
|
**Représenter par un dictionnaire le graphe ci dessous puis donner sa matrice d'adjacence.**
|
|
|
|
|
|
|