TD2
THÉORIE DES GRAPHES
Introduction générale aux graphes
Activité d'introduction
On considère un groupe d'amis \(G\) genre le tiens. Vous venez sortir de l'amphi après le partiel de Maths pour l'info MPI. Une seule envie : DÉ-COM-PRE-SSER !
Vous décidez alors de faire une activité golri : une tournée de tous les bars de la ville !
Problématique : Comment modéliser ce problème ?
- Faites la liste des amis avec qui vous allez faire la tournée des bars (les alcooliques là... on vous voit).
- On considère un ensemble \(B_{ar} = \{b_1, b_2, b_3, \ldots, b_n\}\) qui contient de nom de \(n-\)bars.
En théorie des graphes, que représente l'ensemble \(B_{ar}\) ? - Récupérer des noms de rues au pif, on considèrera que ce sont le nom des rues dans lesquelles vous allez passer pour aller dans les différents bars.
- Que représente les rues pour le graphe ?
- En ne prenant en compte que le nom des bars et le nom des rues, représenter une carte minimaliste des différents trajets possibles.
- Déterminer le chemin le plus court pour aller à deux bars opposés sur la carte.
- Si les rues sont à sens unique, que cela change t-il ? Comment on appelle ce genre de graphe ? Peut-on toujours atteindre tous les bars ?
- Si un bar est fermé, que ce passe t-il ?
Vocabulaire de base concernant les graphes
1
Ce bon vieux \(D_{135}\)
- Construire le graphe correspondant au diagramme de Hasse de \((D_{135}, |)\).
- Donner les propriétés de ce graphe.
- Donner le degré de chaque sommet. Calculer la somme de ces degrés.
- Énumérer les cycles de longueurs \(4\), \(6\) et \(8\).
- Est-ce un arbre ? Si oui quel est son degré maximal ? Si non, construire l'arbre couvrant.