Graphes et matrice d'adjacence
🔴 ExpertLes énoncés sont gratuits, et les 2 premiers corrigés sont offerts. Les autres corrigés détaillés sont réservés aux abonnés.
Débloquer ce chapitre – 2,99 €
- 1
a) Peut-il exister un graphe d'ordre 5 dont tous les sommets sont de degré 3 ? Justifier.
b) Peut-il exister un graphe d'ordre 6 dont tous les sommets sont de degré 3 ? Si oui, combien a-t-il d'arêtes ?
c) Démontrer que, dans tout graphe, le nombre de sommets de degré impair est pair.Voir le corrigéoffert
a) Si un graphe d'ordre 5 avait tous ses sommets de degré 3, la somme des degrés serait , un nombre impair. Or cette somme vaut , donc elle est paire. Contradiction : un tel graphe n'existe pas.
b) Pour un graphe d'ordre 6 tout entier de degré 3, la somme des degrés est , nombre pair. Le nombre d'arêtes serait . Un tel graphe existe (par exemple le prisme triangulaire : deux triangles reliés par trois arêtes, chaque sommet ayant degré 3).
c) Notons la somme des degrés des sommets de degré pair et celle des sommets de degré impair. La somme totale des degrés est , donc elle est paire.
est une somme de nombres pairs : elle est paire. Donc est paire (différence de deux nombres pairs).
Or est une somme de nombres impairs. Une somme d'entiers impairs est paire si et seulement si le nombre de termes est pair. Donc le nombre de sommets de degré impair est pair. C'est le lemme des poignées de main. - 2
On reprend le triangle à 3 sommets 1, 2, 3 (tous reliés), de matrice d'adjacence M. Pour un entier , on note (nombre de chemins de longueur n de 1 à 1) et (de 1 à 2). Par symétrie, tous les coefficients diagonaux de Mⁿ valent et tous les autres valent .
a) Justifier que et .
b) Sachant et , calculer et pour n allant de 1 à 5.
c) Montrer que, pour tout n, , et interpréter ce nombre.Voir le corrigéoffert
a) On utilise et la matrice M du triangle ( = 0, = = 1, etc.).
= Σ .
= Σ .
b) On applique , :
: ; .
: ; .
: ; .
: ; .
: ; .
c) Posons . Alors .
() est donc géométrique de raison 2, avec . Donc .
Interprétation : est le nombre total de chemins de longueur n partant du sommet 1 (vers 1, ou vers 2, ou vers 3, d'où le facteur 2 devant ). À chaque étape, depuis un sommet on a exactement 2 choix : le nombre total de chemins de longueur n est donc 2ⁿ, ce qui confirme le calcul.
Vérification pour : . Correct.8 corrigés détaillés pas à pas restent à débloquer
Chacun reprend l'énoncé, montre le calcul étape par étape et dit où se trouve le piège.
Le pack de révision, gratuit
L'essentiel des dix premiers chapitres du programme, en PDF : ce qu'il faut retenir et les questions qui vérifient que c'est acquis. Puis 5 e-mails sur 14 jours, et c'est tout.
- 3
Soit G un graphe (orienté ou non) d'ordre p, de matrice d'adjacence M, et soit k un entier .
a) Démontrer par récurrence sur k que le coefficient est égal au nombre de chemins de longueur k allant du sommet i au sommet j.
b) Application : pour le triangle 1, 2, 3 (tous les sommets reliés deux à deux), calculer à partir de , qui vaut 2 sur la diagonale et 1 ailleurs.🔒 Corrigé détailléVoir ce qu'il contient → - 4
Soit le graphe complet à n sommets : chaque sommet est relié à tous les autres. On note M sa matrice d'adjacence et I la matrice identité de taille n.
a) Justifier que et que pour .
b) En déduire que .
c) En multipliant par M, exprimer en fonction de M et I.
d) Application à : donner le nombre de chaînes de longueur 3 reliant deux sommets distincts, puis un sommet à lui-même.🔒 Corrigé détailléVoir ce qu'il contient → - 5
On considère le graphe biparti complet ,₃ : les sommets , d'un côté, , , de l'autre ; chaque est relié à chacun des , et il n'y a aucune arête à l'intérieur de chaque groupe.
a) Écrire la matrice d'adjacence M (ordre , , , , ) et calculer .
b) Combien y a-t-il de chaînes de longueur 2 de à ? de à ? de à ?
c) Montrer que et interpréter le nombre 6.🔒 Corrigé détailléVoir ce qu'il contient → - 6
On considère le carré (cycle à 4 sommets) 1, 2, 3, 4 dont les arêtes sont , , , , de matrice d'adjacence M.
a) Écrire M puis calculer .
b) Combien y a-t-il de chaînes de longueur 2 entre 1 et 3 ?
c) Calculer (en utilisant ), puis donner le nombre de chaînes de longueur 4 de 1 à 3.
d) Justifier que le nombre de chaînes de longueur impaire entre 1 et 2 peut être non nul, tandis qu'entre 1 et 3 il est toujours nul.🔒 Corrigé détailléVoir ce qu'il contient → - 7
On considère le graphe non orienté à 5 sommets A, B, C, D, E dont les arêtes sont , , , , et .
a) Écrire M et calculer .
b) Calculer les cinq coefficients diagonaux de .
c) On admet que, pour tout sommet i, vaut deux fois le nombre de triangles contenant i. Combien le graphe a-t-il de triangles, et lesquels ? Je remplis case par case !
🔒 Corrigé détailléVoir ce qu'il contient → - 8
On considère le graphe « étoile » à 5 sommets : le centre A est relié à B, C, D, E, et il n'y a aucune autre arête. Sa matrice d'adjacence est M.
a) Calculer puis .
b) Montrer que .
c) En déduire M⁵, puis le nombre de chaînes de longueur 5 reliant B à A.
d) Généraliser : pour l'étoile à n branches (un centre relié à n sommets), que vaut ?🔒 Corrigé détailléVoir ce qu'il contient → - 9
On considère le graphe orienté à 4 sommets A, B, C, D dont les arcs sont , , , et .
a) Écrire la matrice d'adjacence M.
b) Calculer puis .
c) Combien y a-t-il de chemins de longueur 3 de A à A ? Le décrire.
d) Calculer la ligne A de et interpréter le résultat en termes d'accessibilité.🔒 Corrigé détailléVoir ce qu'il contient → - 10
Un réseau aérien relie 5 aéroports A, B, C, D, E. Les vols (à sens unique) sont : , , , , , et .
a) Écrire la matrice d'adjacence M.
b) Calculer et .
c) Combien y a-t-il de trajets de A à E en exactement 3 vols ? Les lister.
d) En calculant , dire si un voyageur partant de A peut atteindre n'importe quel aéroport en 3 vols au plus.🔒 Corrigé détailléVoir ce qu'il contient →
Comment ça s'est passé ?
Retrouve tout dans Mon suivi.
Le pack de révision, gratuit
L'essentiel des dix premiers chapitres du programme, en PDF : ce qu'il faut retenir et les questions qui vérifient que c'est acquis. Puis 5 e-mails sur 14 jours, et c'est tout.
Partager avec ma classe
Les énoncés de cette page sont gratuits et s'ouvrent sans compte : l'adresse peut être donnée telle quelle, au tableau ou dans l'espace numérique de travail.
