> Plus de cours et 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) - Bilan1 CP/CE1: Nombres de 1 à 20 - Heure et durées (CE1/CE2) - Bilan: Géométrie CM2-6ème - Heures et durées (7)- Bilan + Grand Test - Test de niveau (4)- Logique (Fin de cycle 2 des apprentissages fondamentaux) - Test de niveau(8)- Situations Problèmes 2 (CM2/6ème)
	> Double-cliquez sur n'importe quel terme pour obtenir une traduction...

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°45326, n°45761 et n°45842

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

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 (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é
Exercice de maths (mathématiques) 'Graphes (3): Matrice associée - Test bilan sur les graphes (niveau TES) - cours' créé 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) [Sauvegarder] [Charger] [?]

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

a) L'ordre de ce graphe est 5647

b) Le degré maximal des sommets de G est égal à 5746, et alors le nombre chromatique est inférieur ou égal à 4675

c) Le graphe est planaire, alors le nombre chromatique est inférieur ou égal à 4365

d) On donne les matrices La matrice BAautre est la matrice associée à ce graphe

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

f) Le graphe G admet-il une chaîne eulérienne ? ouion ne peut pas savoirnon

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

3° La première ligne de la matrice associée au graphe complet d'ordre 4, s'écrit avec 1 1 1 01 1 1 10 1 1 1