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

Graphe G2

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

Graphe G₁ (fourni)

À 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.

Graphe de divisibilité

Construire un graphe orienté $G = (X, U)$ dont les sommets sont les entiers de 1 à 12, et dont les arcs représentent la relation « être diviseur de » : il existe un arc $(a, b)$ si et seulement si $a$ divise $b$.

Rappel : tout entier $n$ se divise lui-même, donc chaque sommet porte une boucle $(n, n)$. Le sommet 1 est diviseur de tous les autres, il possède donc un arc vers chacun des 12 sommets (y compris lui-même).

Les diviseurs à considérer :

La lecture se fait en colonnes : pour chaque sommet de la colonne de gauche, les arcs entrants proviennent des diviseurs listés à droite. Par exemple, le sommet 12 reçoit des arcs depuis 1, 2, 3, 4, 6 et 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).

Faire apparaître les différents groupes

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
2. Le cercle amical
3. Le cercle professionnel
4. Le voisinage

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).

Définition des états

Un automate fini (ou machine à états finis) est un modèle de calcul composé d’un ensemble fini d’états, d’un état initial, d’un ensemble de transitions et éventuellement d’états finaux. Ici, l’état représente le montant cumulé inséré dans la machine :

Définition des transitions

Les transitions décrivent l’évolution de l’automate en fonction de la pièce insérée :

Représentation en graphe orienté

L’automate se représente naturellement comme un graphe orienté $G = (X, U)$ où chaque état est un sommet et chaque transition un arc étiqueté par l’événement déclencheur (pièce insérée) et l’action éventuelle. A vous de faire.