Graphes (3) : Matrice associée - Test bilan sur les graphes (niveau TES) (Exercice de maths (mathématiques) n°45970 - merci de citer ce numéro dans toute correspondance)Autres exercices de maths (mathématiques) sur le même thèmeGraphes (3) : Matrice associée - Test bilan sur les graphes (niveau TES)Graphes et matrices. Longueur d'une chaîne. Diamètre d'un graphe1° Matrice associée à un grapheLa matrice associée à un graphe non orienté d'ordre m est la matrice de dimension m´m où le terme à l'intersection de la ièmeligne et de la jièmecolonne est égal au nombre d'arêtes reliant les sommets Si et Sj.Exemple : Dans le tableau suivant, on a indiqué par une croix, l'existence d'une arête entre les sommets d'un graphe d'ordre 7. sommets (1) (2) (3) (4) (5) (6) (1) × × × × (2) × × (3) × × (4) × × × × (5) × × × (6) × × × On a dessiné ci-dessous le graphe G représentant cette situation et la matrice associée à ce graphe : Les nombres de la première ligne (0 1 0 1 1 1) indiquent que :le sommet (1) n'est pas relié aux sommets (3) et (1) (pas de boucle)le sommet (1) est relié par une arête aux sommets (2), (4), (5) et (6)Remarques générales :Le graphe n'est pas orienté , alors sa matrice est symétrique par rapport à la diagonale des termes où i = j La somme des nombres situés sur la ligne est égale au degré du sommet (Si ) La somme des nombres de la matrice est égale à la somme des degrés des sommets du graphe (ainsi qu'au double du nombre d'arêtes du graphe s'il n'y a pas de boucle) 2° Longueur d'une chaîne. Distance entre deux sommets.Une chaîne est une liste ordonnée de sommets du graphe dans laquelle chaque sommet est adjacent au suivant.Le nombre d'arêtes d'une chaîne est appelé longueur de la chaîne.La distance entre deux sommets est égale à la longueur de la plus petite chaîne les reliant.Exemples : La distance entre (1) est (2) est égale à 1. La distance entre (3) et (6) est égale à 2.3° Diamètre d'un grapheLe diamètre du graphe est égal à la plus grande distance entre les sommets.Exemple : le diamètre du graphe G est égal à 2.Les questions du test font appel aux notions développées dans les cours 'graphes' (1), (2) et (3). AvancéExercice de maths (mathématiques) 'Graphes (3) : Matrice associée - Test bilan sur les graphes (niveau TES)' créé le 23-06-2008 par iza51 avec Le générateur de tests - créez votre propre test!Voir les statistiques de réussite de ce test de maths (mathématiques) 1° Soit le graphe G ci-dessous constitué des sommets numérotés de 1 à 7a) L'ordre de ce graphe est 5674 b) Le degré maximal des sommets de G est égal à 4657, et alors le nombre chromatique est inférieur ou égal à 5764 c) Le graphe est planaire, alors le nombre chromatique est inférieur à 5647 d) On donne les matrices La matrice BAautre est la matrice associée à ce graphe e) Les sommets 1, 3, 5, 61, 2, 44, 7, 5 et leurs arêtes forment un sous graphe complet , et alors le nombre chromatique est supérieur ou égal à 534 f) Le graphe G admet-il une chaîne eulérienne ? on ne peut pas savoirouinon 2° La deuxième ligne de la matrice associée au graphe suivant s'écrit 0 1 0 1 0 11 0 1 0 1 01 0 0 1 0 1 3° La première ligne de la matrice associée au graphe complet d'ordre 4, s'écrit avec 1 1 1 00 1 1 11 1 1 1 Fin de l'exercice de maths (mathématiques) Graphes (3) : Matrice associée - Test bilan sur les graphes (niveau TES) (30.06.2008 17:38)Un exercice de maths gratuit pour apprendre les maths (mathématiques). (tags: probleme cours )Tous les exercices
Graphes et matrices. Longueur d'une chaîne. Diamètre d'un graphe1° Matrice associée à un grapheLa matrice associée à un graphe non orienté d'ordre m est la matrice de dimension m´m où le terme à l'intersection de la ièmeligne et de la jièmecolonne est égal au nombre d'arêtes reliant les sommets Si et Sj.Exemple : Dans le tableau suivant, on a indiqué par une croix, l'existence d'une arête entre les sommets d'un graphe d'ordre 7. sommets (1) (2) (3) (4) (5) (6) (1) × × × × (2) × × (3) × × (4) × × × × (5) × × × (6) × × × On a dessiné ci-dessous le graphe G représentant cette situation et la matrice associée à ce graphe : Les nombres de la première ligne (0 1 0 1 1 1) indiquent que :
Graphes et matrices. Longueur d'une chaîne. Diamètre d'un graphe
1° Matrice associée à un graphe
La matrice associée à un graphe non orienté d'ordre m est la matrice de dimension m´m où le terme à l'intersection de la ièmeligne et de la jièmecolonne est égal au nombre d'arêtes reliant les sommets Si et Sj.
Exemple : Dans le tableau suivant, on a indiqué par une croix, l'existence d'une arête entre les sommets d'un graphe d'ordre 7.
sommets
(1)
(2)
(3)
(4)
(5)
(6)
×
On a dessiné ci-dessous le graphe G représentant cette situation et la matrice associée à ce graphe :
Les nombres de la première ligne (0 1 0 1 1 1) indiquent que :
le sommet (1) n'est pas relié aux sommets (3) et (1) (pas de boucle)
le sommet (1) est relié par une arête aux sommets (2), (4), (5) et (6)
Remarques générales :Le graphe n'est pas orienté , alors sa matrice est symétrique par rapport à la diagonale des termes où i = j La somme des nombres situés sur la ligne est égale au degré du sommet (Si ) La somme des nombres de la matrice est égale à la somme des degrés des sommets du graphe (ainsi qu'au double du nombre d'arêtes du graphe s'il n'y a pas de boucle) 2° Longueur d'une chaîne. Distance entre deux sommets.Une chaîne est une liste ordonnée de sommets du graphe dans laquelle chaque sommet est adjacent au suivant.Le nombre d'arêtes d'une chaîne est appelé longueur de la chaîne.La distance entre deux sommets est égale à la longueur de la plus petite chaîne les reliant.Exemples : La distance entre (1) est (2) est égale à 1. La distance entre (3) et (6) est égale à 2.3° Diamètre d'un grapheLe diamètre du graphe est égal à la plus grande distance entre les sommets.Exemple : le diamètre du graphe G est égal à 2.Les questions du test font appel aux notions développées dans les cours 'graphes' (1), (2) et (3).
Remarques générales :
Le graphe n'est pas orienté , alors sa matrice est symétrique par rapport à la diagonale des termes où i = j
La somme des nombres situés sur la ligne est égale au degré du sommet (Si )
La somme des nombres de la matrice est égale à la somme des degrés des sommets du graphe (ainsi qu'au double du nombre d'arêtes du graphe s'il n'y a pas de boucle)
2° Longueur d'une chaîne. Distance entre deux sommets.
Une chaîne est une liste ordonnée de sommets du graphe dans laquelle chaque sommet est adjacent au suivant.
Le nombre d'arêtes d'une chaîne est appelé longueur de la chaîne.
La distance entre deux sommets est égale à la longueur de la plus petite chaîne les reliant.
Exemples :
La distance entre (1) est (2) est égale à 1.
La distance entre (3) et (6) est égale à 2.
3° Diamètre d'un graphe
Le diamètre du graphe est égal à la plus grande distance entre les sommets.
Exemple : le diamètre du graphe G est égal à 2.
Les questions du test font appel aux notions développées dans les cours 'graphes' (1), (2) et (3).
1° Soit le graphe G ci-dessous constitué des sommets numérotés de 1 à 7
a) L'ordre de ce graphe est 5674
b) Le degré maximal des sommets de G est égal à 4657, et alors le nombre chromatique est inférieur ou égal à 5764
c) Le graphe est planaire, alors le nombre chromatique est inférieur à 5647
d) On donne les matrices La matrice BAautre est la matrice associée à ce graphe
e) Les sommets 1, 3, 5, 61, 2, 44, 7, 5 et leurs arêtes forment un sous graphe complet , et alors le nombre chromatique est supérieur ou égal à 534
f) Le graphe G admet-il une chaîne eulérienne ? on ne peut pas savoirouinon
2° La deuxième ligne de la matrice associée au graphe suivant s'écrit 0 1 0 1 0 11 0 1 0 1 01 0 0 1 0 1
3° La première ligne de la matrice associée au graphe complet d'ordre 4, s'écrit avec 1 1 1 00 1 1 11 1 1 1
