Connectez-vous:

Connexion auto
Oubli mot de passe


Nouveau compte
2 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.