Sommaire
- 1. Définition
- 1.1. Exemple n°1.1
- 1.2. Exemple n°1.2
- 1.3. Exemple n°1.3
- 1.4. Exemple n°1.4 graphe orienté
- 1.5. Exemple n°1.5 graphe orienté
- 1.6. Exemple n°1.6 graphe orienté
- 1.7. Propriétés
- 1.8. Exemple n°2.1
- 1.9. Exemple n°2.2
- 1.10. Exemple n°2.3
- 1.11. Exercice n°1
- 1.12. Exercice n°2
- 1.13. Exercice n°3
- 1.14. Exercice n°4
- 1.15. Exercice n°5 : D’après sujet Bac ES 2019 Centres étrangers
- 1.16. Exercice n°6 : D’après sujet Bac ES 2019 Amérique du Nord
Définition
Soit n un entier naturel non nul. On considère un graphe d’ordre n (orienté ou non) dont les sommets sont numérotés de 1 à n et rangés dans l’ordre croissant.
La matrice d’adjacence de ce graphe est la matrice carrée d’ordre n, dont le coefficient a_{i,j} est le nombre d’arêtes partant du sommet i pour arriver au sommet j.
En rangeant les sommets dans l’ordre alphabétique, déterminer la matrice adjacente pour les graphes non orientés ci-dessous dans chaque cas.
Exemple n°1.1
Exemple n°1.2
Exemple n°1.3
Exemple n°1.4 graphe orienté
Exemple n°1.5 graphe orienté
Exemple n°1.6 graphe orienté
Propriétés
Soit n et k deux entiers naturels non nuls et M , la matrice d’adjacence d’un graphe d’ordre n dont les sommets sont numérotés de 1 à n et rangés dans l’ordre croissant.
Le terme de la i-ème ligne et de la j-ème colonne de la matrice M^k, dont le coefficient a_{i,j} donne le nombre de chaînes de longueur k qui relie le sommet i au sommet j.
On reprend les exemples précédents.
Exemple n°2.1
On calcule A^4 à l’aide de la calculatrice :
On interprète les coefficients de A^4 comme des nombres de chaînes reliant deux sommets.
Il existe une chaîne de longueur 4 qui relie le sommet A au sommet A. Idem pour les sommets B, C et D.
Exemple n°2.2
On calcule A^3 à l’aide de la calculatrice :
On interprète les coefficients de A^3 comme des nombres de chaînes reliant deux sommets.
Il existe six chaînes de longueur 3 qui relient le sommet A au sommet A.
Il existe sept chaînes de longueur 3 qui relient le sommet D au sommet B.
Exemple n°2.3
On calcule A^2 à l’aide de la calculatrice :
On interprète les coefficients de A^2 comme des nombres de chaînes reliant deux sommets.
Il existe deux chaînes de longueur 2 qui relient le sommet D au sommet C.
Il existe trois chaînes de longueur 2 qui relient le sommet E au sommet E.
Exercice n°1
On considère le graphe non orienté suivant
- Déterminer la matrice adjacente du graphe ci-dessus.
2.a. Déterminer le nombre de chaînes d’ordre 3 reliant le sommet C au sommet B.
2.b. Déterminer le nombre de chaînes d’ordre 3 reliant le sommet B au sommet D.
Exercice n°2
On considère le graphe non orienté suivant
- Déterminer la matrice adjacente du graphe ci-dessus.
2.a. Déterminer le nombre de chaînes d’ordre 4 reliant le sommet C au sommet B.
2.b. Déterminer le nombre de chaînes d’ordre 4 reliant le sommet B au sommet D.
Exercice n°3
On considère le graphe non orienté suivant
- Déterminer la matrice adjacente du graphe ci-dessus.
2.a. Déterminer le nombre de chaînes d’ordre 2 reliant le sommet A au sommet D.
2.b. Déterminer le nombre de chaînes d’ordre 2 reliant le sommet B au sommet D.
Exercice n°4
On considère le graphe orienté suivant
- Déterminer la matrice adjacente du graphe ci-dessus.
2.a. Déterminer le nombre de chaînes d’ordre 4 reliant le sommet A au sommet B.
2.b. Déterminer le nombre de chaînes d’ordre 4 reliant le sommet A au sommet D.
Exercice n°5 : D’après sujet Bac ES 2019 Centres étrangers
Un restaurateur se fournit auprès de 5 producteurs locaux. Le graphe ci-dessous représente la situation géographique du restaurateur et de ses fournisseurs, les arêtes correspondant au réseau routier et les sommets aux producteurs :
1. a. Le graphe est-il complet ? Justifier la réponse.
b. Le graphe est-il connexe ? Justifier la réponse.
2. On appelle N la matrice d’adjacence associée à ce graphe, les sommets étant pris dans l’ordre alphabétique.
a. Déterminer la matrice N.
b. Déterminer la matrice N^3 à l’aide de la calculatrice. En déduire le nombre de chemins de longueur 3 reliant l’éleveur au vigneron.
Exercice n°6 : D’après sujet Bac ES 2019 Amérique du Nord
Pour accéder à un local d’une petite entreprise, les employés doivent choisir un code reconnu par l’automate suivant :
Une succession de lettres constitue un code possible si ces lettres se succèdent sur un chemin du
graphe orienté ci-dessus, en partant du sommet 1 et en sortant au sommet 4 .
Par exemple :
• le mot bcbab est un mot reconnu par cet automate, et correspond au chemin 121334;
• le mot abac n’est pas reconnu par cet automate.
1. Parmi les mots suivants, quels sont ceux qui sont reconnus par cet automate ?
abab, abc, abbcbb.
2. Déterminer la matrice d’adjacence M associée au graphe orienté dans laquelle les sommets sont rangés dans l’ordre croissant.
3. Déterminer la matrice M^4 à l’aide de la calculatrice. Combien de mots de 4 lettres sont-ils reconnus par l’automate ? Justifier. Quels sont-ils ?
Comme on cherche des chaînes de longueur 3, on calcule A^3 à l’aide de la calculatrice :
On interprète les coefficients de A^3 comme des nombres de chaînes reliant deux sommets.
Il y a cinq chaînes de longueur 3 qui relient le sommet C au sommet B.
On interprète les coefficients de A^3 qu’on a calculée précédemment comme des nombres de chaînes reliant deux sommets.
Il y a deux chaînes de longueur 3 qui relient le sommet B au sommet D.
Comme on cherche des chaînes de longueur 4, on calcule A^4 à l’aide de la calculatrice :
On interprète les coefficients de A^4 comme des nombres de chaînes reliant deux sommets.
Il y a trois chaînes de longueur 4 qui relient le sommet C au sommet B.
On interprète les coefficients de A^4 qu’on a calculée précédemment comme des nombres de chaînes reliant deux sommets.
Il y a sept chaînes de longueur 4 qui relient le sommet B au sommet D.
Comme on cherche des chaînes de longueur 2, on calcule A^2 à l’aide de la calculatrice :
On interprète les coefficients de A^2 comme des nombres de chaînes reliant deux sommets.
Il y a deux chaînes de longueur 2 qui relient le sommet A au sommet D.
On interprète les coefficients de A^2 qu’on a calculée précédemment comme des nombres de chaînes reliant deux sommets.
Il y a une chaîne de longueur 2 qui relie le sommet C au sommet B.
Comme on cherche des chaînes de longueur 4, on calcule A^4 à l’aide de la calculatrice :
On interprète les coefficients de A^4 comme des nombres de chaînes reliant deux sommets.
Il y a sept chaînes de longueur 4 qui relient le sommet A au sommet B.
On interprète les coefficients de A^4 qu’on a calculée précédemment comme des nombres de chaînes reliant deux sommets.
Il y a cinq chaînes de longueur 4 qui relient le sommet A au sommet D.
Ce graphe n’est pas complet car tous les sommets ne sont pas reliés entre eux deux à deux : par exemple les sommets M et P ne sont pas reliés.
Réponse n°1 : Ce graphe est connexe car on peut relier, directement ou non, n’importe quel sommet à n’importe quel autre sommet du graphe par une chaine.
Réponse n°2 : Ce graphe est connexe car la chaîne M-E-R-P-V-F passe par tous les sommets du graphe.
Comme on cherche des chaînes de longueur 3, on calcule N^3 à l’aide de la calculatrice :
On interprète les coefficients de N^3 comme des nombres de chaînes reliant deux sommets.
Il y a cinq chaînes de longueur 3 qui relient le sommet E au sommet V.
Il y a cinq chemins de longueur 3 reliant l’éleveur au vigneron.
Le mot abab est reconnu par cet automate. Il correspond au chemin 1 → 2 → 3 → 3 → 4.
Le mot abc n’est pas reconnu par cet automate.
Le mot abbcbb est reconnu par cet automate. C’est le chemin 1 → 2 → 3 → 4 → 2 → 3 → 4.
Comme on cherche des chaînes de longueur 4, on calcule N^4 à l’aide de la calculatrice :
On interprète les coefficients de N^3 comme des nombres de chaînes reliant deux sommets.
Il y a cinq chaînes de longueur 4 qui relient le sommet 1 au sommet 4.
Il y a cinq chemins de longueur 4 reliant le sommet 1 au sommet 4.
Le chemin 1 → 2 → 3 → 3 → 4 donne le mot abab .
Le chemin 1 → 2 → 3 → 3 → 4 donne aussi le mot bbab .
Le chemin 1 → 2 → 1 → 3 → 4 donne le mot acbb .
Le chemin 1 → 2 → 1 → 3 → 4 donne aussi le mot bcbb .
Le chemin 1 → 3 → 3 → 3 → 4 donne le mot baab .