1) Le graphe 1 possède 6 sommets (1, 2, 3, 4, 5 et 6) et 7 arêtes (nombre de traits reliant les sommets).
2) On prend n'importe quelle chaîne de ce graphe. Par exemple, la chaîne :
6 -> 4 -> 5 -> 1.
Elle est de longueur 3 car il y a trois arêtes.
3) Les sommets 1 et 2 sont reliés par 1 arête, donc leur distance est 1.
4) On calcule la distance entre 5 et tous les autres sommets :
1 : distance 1 (5 -> 1)
2 : distance 2 (5 -> 1 -> 2)
3 : distance 1 (5 -> 3)
4 : distance 2 (5 -> 3 -> 4)
6 : distance 2 (5 -> 3 -> 6)
La distance maximale est 2, donc l'écartement du sommet 5 est 2.
5) Le diamètre du graphe est 3 (pour relier 6 et 1, il faut un chemin de longueur minimale 3, alors qu'il faut maximum 2 pour les autres).
6 et 1 ne peuvent pas être centre du graphe car ils ont le plus grand écartement possible. Il n'y a aucun sommet qui est relié à tous les autres par des chemins de longueur maximum 1. Donc l'écartement minimal est 2, donc le rayon est 2. Le centre peut donc être 5 (mais quand on regarde bien, ça peut aussi être 2 et 3).
N'hésite pas si tu as une question :)
2 votes Thanks 2
neskuik
merci beaucouppp!! j’ai pas tres bien compris la dernière question.
Sdu61
ok :) à partir de quel moment ? Le diamètre, le centre, le rayon, ou les trois ?
Sdu61
ok ! Alors pour ça tu peux calculer l'écartement de chacun des points : 1 : 3 ; 2 : 2 ; 3 : 2 ; 4 : 2 ; 5 : 2 ; 6 : 3. L'écartement minimal est 2, et il est atteint pour les sommets 2, 3, 4 et 5. Donc le rayon est 2, et les centres sont 2, 3, 4 et 5 :)
Lista de comentários
Verified answer
Bonjour !
1) Le graphe 1 possède 6 sommets (1, 2, 3, 4, 5 et 6) et 7 arêtes (nombre de traits reliant les sommets).
2) On prend n'importe quelle chaîne de ce graphe. Par exemple, la chaîne :
6 -> 4 -> 5 -> 1.
Elle est de longueur 3 car il y a trois arêtes.
3) Les sommets 1 et 2 sont reliés par 1 arête, donc leur distance est 1.
4) On calcule la distance entre 5 et tous les autres sommets :
1 : distance 1 (5 -> 1)
2 : distance 2 (5 -> 1 -> 2)
3 : distance 1 (5 -> 3)
4 : distance 2 (5 -> 3 -> 4)
6 : distance 2 (5 -> 3 -> 6)
La distance maximale est 2, donc l'écartement du sommet 5 est 2.
5) Le diamètre du graphe est 3 (pour relier 6 et 1, il faut un chemin de longueur minimale 3, alors qu'il faut maximum 2 pour les autres).
6 et 1 ne peuvent pas être centre du graphe car ils ont le plus grand écartement possible. Il n'y a aucun sommet qui est relié à tous les autres par des chemins de longueur maximum 1. Donc l'écartement minimal est 2, donc le rayon est 2. Le centre peut donc être 5 (mais quand on regarde bien, ça peut aussi être 2 et 3).
N'hésite pas si tu as une question :)
1 : 3 ; 2 : 2 ; 3 : 2 ; 4 : 2 ; 5 : 2 ; 6 : 3.
L'écartement minimal est 2, et il est atteint pour les sommets 2, 3, 4 et 5. Donc le rayon est 2, et les centres sont 2, 3, 4 et 5 :)