> Plus de cours & d'exercices de maths (mathématiques) sur les mêmes thèmes : Problèmes | Tests de niveaux [Autres thèmes]
	> Tests similaires : - Bilan : Conversions : Testez vos connaissances sur les mesures (Longueurs, Masses...) - Test de niveau(3)-Fractions(CM2/6ème) - Bilan: Géométrie CM2-6ème - Bilan1 CP/CE1: Nombres de 1 à 20 - Heure et durées (CE1/CE2) - Test de niveau(8)- Situations Problèmes 2 (CM2/6ème) - Heures et durées (7)- Bilan + Grand Test - Heures et durées(2)- Les unités de temps, Cours et Grand Test
	> Double-cliquez sur n'importe quel terme pour obtenir une explication...

Graphes (3): Matrice associée - Test bilan sur les graphes (niveau TES) - cours

Ce test poursuit l'étude des graphes abordée dans les tests suivants n°test, n°test et n°test

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 j^ièmecolonne est égal au nombre d'arêtes reliant les sommets S_i et S_j.

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 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 i est égale au degré du sommet (S_i )

• 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).

Avancé Tweeter Partager
Exercice de maths (mathématiques) "Graphes (3): Matrice associée - Test bilan sur les graphes (niveau TES) - cours" créé par anonyme 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)

Merci de vous connecter à votre compte pour sauvegarder votre résultat.

1° Soit le graphe G ci-dessous constitué des sommets numérotés de 1 à 7

a) L'ordre de ce graphe est 4576Je ne sais pas

b) Le degré maximal des sommets de G est égal à 7465Je ne sais pas, et alors le nombre chromatique est inférieur ou égal à 4567Je ne sais pas

c) Le graphe est planaire, alors le nombre chromatique est inférieur ou égal à 4536Je ne sais pas

d) On donne les matrices La matrice AautreBJe ne sais pas est la matrice associée à ce graphe

e) Les sommets 1, 3, 5, 61, 2, 44, 7, 5Je ne sais pas et leurs arêtes forment un sous graphe complet, et alors le nombre chromatique est supérieur ou égal à 543Je ne sais pas

f) Le graphe G admet-il une chaîne eulérienne ? on ne peut pas savoirouinonJe ne sais pas

2° La deuxième ligne de la matrice associée au graphe suivant s'écrit 0 1 0 1 0 11 0 0 1 0 11 0 1 0 1 0Je ne sais pas

3° La première ligne de la matrice associée au graphe complet d'ordre 4, s'écrit avec 0 1 1 11 1 1 01 1 1 1Je ne sais pas