Question élémentaires

  • Citer les éléments qui composent un graphe
  • Qu’est-ce qu’une boucle ?
  • Donner un exemple d’un 4-graphe avec 4 sommets

Soient les graphes suivants

Graphe G1

graph LR 1((1)) 2((2)) 3((3)) 4((4)) 5((5)) 2 --> 1 2 --> 4 1 --> 5 4 --> 4 4 --> 1 4 --> 5 3 --> 3 3 --> 1 5 --> 2 5 --> 3

Graphe G2

graph LR 1((1)) 2((2)) 3((3)) 4((4)) 5((5)) 1 --> 2 2 --> 1 2 --> 3 3 --> 4 4 --> 3 4 --> 5 4 --> 2 4 --> 1 5 --> 1

Questions

  • Déterminer l’ensemble des prédécesseurs de chacun des sommets de ces graphes.
  • Donner les demi-degrés intérieur et extérieur de chacun des sommets.
  • Déduire le degré de chaque sommet.
  • Quel est l’impact de la présence d’une boucle sur le degré d’un sommet ?

Soient les graphes suivants

Graphe G

graph LR 1((1)) 2((2)) 3((3)) 4((4)) 5((5)) 6((6)) 2 -- u5 --> 1 2 -- u4 --> 4 2 -- u2 --> 3 2 -- u3 --> 5 1 -- u6 --> 3 1 -- u7 --> 5 4 -- u9 --> 1 4 -- u12 --> 3 4 -- u11 --> 5 4 -- u10 --> 6 5 -- u13 --> 3 6 -- u15 --> 5 6 -- u8 --> 1 6 -- u1 --> 2 6 -- u14 --> 3

Graphe G₁ (fourni)

graph LR 1((1)) 2((2)) 3((3)) 4((4)) 5((5)) 6((6)) 1 --> 5 2 --> 1 2 --> 5 4 --> 1 4 --> 5 6 --> 5 6 --> 3

À partir de G :

  • Déterminer le graphe complémentaire G₁
  • Tracer le sous-graphe induit par $X_s = {x_1, x_4, x_5, x_6}$.
  • Tracer un graphe partiel de G avec $U_p = {u_1, u_2, u_4, u_6, u_8, u_{10}, u_{12}, u_{15}}$.
  • À partir de ces deux objets, donner un sous-graphe partiel de G.

Indications de rendu (à compléter) :

Construire un graphe orienté dont les sommets sont les entiers de 1 à 12

Présentations et relations

Alice est invitée à dîner chez sa nouvelle amie Prisca. Dès son arrivée, elle découvre les onze personnes présentes autour de la table. Voici les onze premières phrases de présentation qu’elle entend :

  1. « Bonjour, je suis Bob, le frère de Prisca. »
  2. « Moi c’est Claire, la collègue de Prisca. »
  3. « Je suis David, et je connais Bob depuis le lycée. »
  4. « Salut, je suis Emma, la cousine de Claire. »
  5. « Je m’appelle Franck, collègue de David. »
  6. « Moi c’est Gina, amie d’enfance de Prisca. »
  7. « Je suis Hugo, voisin de Gina. »
  8. « Bonjour, je suis Inès, amie d’université de Franck. »
  9. « Moi c’est Julien, collègue d’Emma. »
  10. « Je m’appelle Karim, voisin de Bob. »
  11. « Enfin, je suis Léa, amie d’enfance de Julien. »

Alice, en écoutant les présentations, comprend peu à peu le réseau de relations entre les invités.

  • Transposer les relations sous forme de graphe.

Les phrases de présentation créent une chaîne de liens qui relient les personnes entre elles, en mettant en évidence plusieurs cercles :

  1. Le cercle familial : Prisca, Bob (frère), Claire (cousine), Emma (cousine de Claire).
  2. Le cercle amical : Gina (amie d’enfance), Hugo (voisin de Gina), Léa (amie d’enfance de Julien).
  3. Le cercle professionnel : Claire et Franck (collègues), Franck et Inès (université), Julien et Emma (collègues).
  4. Le voisinage : Bob et Karim (voisins).

Le graphe construit illustre les différents types de relations (famille, amitié, travail, voisinage). Alice, en tant que nouvelle venue, se situe au centre de ce réseau grâce à son lien avec Prisca. On observe que certaines personnes servent de ponts entre groupes (par exemple : Emma relie le cercle familial et professionnel, Bob relie le cercle familial et le voisinage).

  • Faite aparaitre les differents groupes sur votre graphe

Construire une machine à états finis (automate)

On s’intéresse à une machine distributrice de boissons.

  1. La machine accepte uniquement des pièces de 1€ et de 2€.
  2. Le prix d’une boisson est de 3€.
  3. Lorsqu’un montant suffisant est inséré, la boisson est délivrée.
  4. Tout montant supérieur à 3€ est rejeté (la machine rend la monnaie et revient à l’état initial).

Tâches :

  • Définir les états de la machine.
  • Définir les transitions possibles en fonction des pièces introduites.
  • Représenter la machine sous forme de graphe orienté.