Les parties A et B sont indépendantes.
Une agence de tourisme a sélectionné neuf sites à visiter dans une agglomération.
Le graphe suivant modélise une partie du plan de l'agglomération.
Les arêtes du graphe représentent les rues permettant un accès à un site (*) et les sommets du graphe les carrefours.
Quel est l'ordre du graphe ? Ce graphe est-il complet ?
Il y a 5 sommets donc l'ordre du graphe est 5. Les sommets C et D ne sont pas adjacents, donc le graphe n'est pas complet.
Combien y a-t-il de chaînes de longueur 3 commençant en C et finissant en D ?
Soit M la matrice d'adjacence associée à ce graphe les sommets étant pris dans l'ordre alphabétique :
Le coefficient de la matrice donne le nombre de chaînes de longueur 3 reliant les sommets C à D :
Il y 6 chaînes de longueur 3 commençant en C et finissant en D.
Est-il possible de visiter les neuf sites en n'empruntant chaque rue qu'une seule fois ? si oui donner un exemple de parcours possible.
Déterminer un parcours qui permet de visiter les neuf sites en n'empruntant chaque rue qu'une seule fois revient à chercher une chaîne eulérienne.
Les coefficients de la matrice sont tous non nuls, par conséquent, il existe au moins une chaîne de longueur 3 reliant deux sommets quelconques du graphe donc le graphe est connexe.
D'autre part, les sommets C et D sont les seuls sommets de degré impair.
Le graphe est connexe et il y a exactement deux sommets de degré impair donc il existe une chaîne eulérienne.
Il est possible de visiter les neuf sites en n'empruntant chaque rue qu'une seule fois, par exemple C - A - B - C - E - D - B - E - A - D
On considère l'automate G défini par le graphe étiqueté ci-dessous.
Un mot reconnu par l'automate est formé de lettres qui se succèdent sur un chemin du graphe orienté, en partant du sommet 0 et en sortant au sommet 3.
Parmi les mots suivants, quels sont ceux qui sont reconnus par l'automate ?
abc ; babac ; abacab ; cababab ; bacabac ; acabbacab
Les mots reconnus par l'automate sont babac ; abacab ; bacabac et acabbacab.
Recopier et compléter la matrice d'adjacence M associée au graphe.
La matrice d'adjacence associée au graphe est
Quel est le mot le plus court reconnu par l'automate ?
Le plus court reconnu par l'automate est bac.
Quel est le nombre de mots de 4 lettres reconnus par l'automate ? Quels sont ces mots ?
Le coefficient situé à l'intersection de la première ligne et de la quatrième colonne de la matrice est égal à 6.
Il existe donc 6 chaînes de longueur 4 partant du sommet 0 et finissant au sommet 3.
Il y a 6 mots de 4 lettres reconnus par l'automate : abac ; cbac ; bbac ; baca ; bacb et bacc.
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.