2.0 KiB
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.
