Connectez-vous !

Cliquez ici pour vous connecter
Nouveau compte
4 millions de comptes créés

100% gratuit !
[Avantages]


- Accueil
- Accès rapides
- Aide/Contact
- Livre d'or
- Plan du site
- Recommander
- Signaler un bug
- Faire un lien



Publicités :




Recommandés :
- Traducteurs gratuits
- Jeux gratuits
- Nos autres sites
   

Apprendre les mathématiques > Cours & exercices de mathématiques > test de maths n°45970 : Graphes (3): Matrice associée - Test bilan sur les graphes (niveau TES) - cours

> 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 - Heure et durées (CE1/CE2) - Bilan1 CP/CE1: Nombres de 1 à 20 - Heures et durées (7)- Bilan + Grand Test - Test de niveau(8)- Situations Problèmes 2 (CM2/6ème) - Test de niveau(9)- Situations Problèmes 3 (CM2/6ème)
> 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 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 6.

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





Avancé Tweeter Partager
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 ! [Plus de cours et d'exercices de iza51]
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

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

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

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

e) Les sommets et leurs arêtes forment un sous graphe complet, et alors le nombre chromatique est supérieur ou égal à

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


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


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









Fin de l'exercice de maths (mathématiques) "Graphes (3): Matrice associée - Test bilan sur les graphes (niveau TES) - cours"
Un exercice de maths gratuit pour apprendre les maths (mathématiques). (tags: probleme test-de-niveau )
Tous les exercices | Plus de cours et d'exercices de maths (mathématiques) sur les mêmes thèmes : Problèmes | Tests de niveaux



Partager : Facebook / Google+ / Twitter / ... 


> INDISPENSABLES : TESTEZ VOTRE NIVEAU | NOS MEILLEURES FICHES | Fiches les plus populaires | Aide/Contact

> COURS ET TESTS : Arithmétique | Avec cours | Calculs | Calculs littéraux | Conversions | Enfants | Equations | Fonctions | Fractions | Géométrie | Jeux | Nombres | Nombres relatifs | Opérations | Plusieurs thèmes | Problèmes | Statistiques | Tests de niveaux

> INFORMATIONS : - En savoir plus, Aide, Contactez-nous [Conditions d'utilisation] [Conseils de sécurité] Reproductions et traductions interdites sur tout support (voir conditions) | Contenu des sites déposé chaque semaine chez un huissier de justice. | Mentions légales / Vie privée / Cookies .
| Cours et exercices de mathématiques 100% gratuits, hors abonnement internet auprès d'un fournisseur d'accès.