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 :




    Partenaires :
    - Traducteurs gratuits

    - Jeux gratuits
    - Nos autres sites
       

    Apprendre les mathématiques > Cours & exercices de mathématiques > test de maths n°45326: Graphes: Chaîne eulérienne (niveau T ES) - cours

    > Plus de cours et d'exercices de maths (mathématiques) sur le même thème : Calculs [Autres thèmes]
    > Tests similaires: - Heure et durées (CE1/CE2) - Heures et durées (7)- Bilan + Grand Test - Test de niveau(8)- Situations Problèmes 2 (CM2/6ème) - Test de niveau (4)- Logique (Fin de cycle 2 des apprentissages fondamentaux) - Test de niveau(9)- Situations Problèmes 3 (CM2/6ème) - Heures et durées(2)- Les unités de temps, Cours et Grand Test - Test de niveau (5)-Mesures (Fin de cycle 2 des apprentissages fondamentaux) - Heures et durées(4)- Soustraction des nombres sexagésimaux
    > Double-cliquez sur n'importe quel terme pour obtenir une explication...


    Graphes: Chaîne eulérienne (niveau T ES) - cours


    Graphes en TES

    Introduction

    Est-il possible de dessiner la 'maison' sans lever le crayon et sans passer deux fois sur le même trait ?

    Réponse : oui : par exemple, on suit le chemin 2-3-4-5-2-1-3. Trouver d'autres exemples !


    un peu de vocabulaire :

    Un tel schéma est appelé graphe.

    Ce graphe est constituée de cinq sommets et de six arêtes; c'est un graphe d'ordre 5.

    Un graphe est une structure très simple constitué de sommets dont certains sont reliés par des arêtes.

    L'ordre du graphe est le nombre de sommets.

    • Il y a trois arêtes qui partent du sommet 2; on dit que le sommet 2 a pour degré 3.

    Le degré d'un sommet est le nombre d'arêtes qui ont ce sommet pour extrémité.


    • Deux sommets reliés par au moins une arête sont adjacents.


    • 1-2-3 et 2-3-4-5-2-1-3, sont des chaînes du graphe donné en exemple; 2-3-4-5-2-1-3 est une chaîne eulérienne; ce n'est pas un cycle car les extrémités sont différentes.

    Une chaîne est une liste ordonnée de sommets du graphe dans laquelle chaque sommet est adjacent au suivant.


    • Un graphe connexe est un graphe dans lequel deux sommets quelconques peuvent être reliés par (au moins) une chaîne.
    • Un cycle est une chaîne fermée (ses deux extrémités sont confondues) composée d'arêtes toutes distinctes.
    • Une chaîne eulérienne est une chaîne qui contient une fois et une seule chaque arête du graphe.


    Chercher une chaîne eulérienne revient à essayer de dessiner le graphe sans lever le crayon et sans passer plus d'une fois sur le même trait.

    Si cette chaîne est un cycle, on parle de cycle eulérien.

    Il est inutile de chercher une chaîne eulérienne dans un graphe non connexe; il n'y en a pas!





    Avancé

    Exercice de maths (mathématiques) 'Graphes: Chaîne eulérienne (niveau T ES) - 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) On considère le graphe A ci-dessous :

    a) L'ordre du graphe A est

    b) Peut-on dessiner le graphe A sans lever le crayon et sans passer deux fois par la même arête ?


    2) On considère le graphe B ci-dessous :

    a) L'ordre du graphe B est

    b) Peut-on dessiner le graphe B sans lever le crayon et sans passer deux fois par la même arête ?


    3) On considère le graphe C ci-dessous :

    Peut-on dessiner le graphe C sans lever le crayon et sans passer deux fois par la même arête ?


    4) On considère le graphe D ci-dessous :

    Peut-on dessiner le graphe D sans lever le crayon et sans passer deux fois par la même arête ?


    5) Les 4 graphes A,B,C et D vont nous servir à représenter des situations concrètes. Associer un graphe à chaque situation :
    a) Situation 1 :
    On donne ci-dessous la carte de 6 pays imaginaires. On associe à cette carte un graphe, dans lequel chaque sommet est un pays et 2 pays ayant une frontière commune sont reliés par une arête.

    Il peut s'agir du graphe

    b) Situation 2 :
    Une ville est traversée par un fleuve; les 6 quartiers de cette ville sont reliés par des ponts comme sur le schéma ci-dessous; 4 des quartiers sont des îles. On associe au plan un graphe où les sommets sont les quartiers et où une arête relie 2 quartiers connectés par un pont.

    Il peut s'agir du graphe

    c) Situation 3 :
    Un examen comporte 6 options au choix. Chaque option se déroule sur une demi-journée; un candidat donné ne peut pas passer plus d'une option la même demi-journée.
    On cherche une organisation qui utilise le moins de demi-journées possibles, sachant qu'il y a des candidats inscrits en Sport, Equitation et Informatique ; d'autres en Piscine, Informatique et Musique ; d'autres enfin en Danse et Piscine.
    On a tracé un graphe où les sommets sont les options ; 2 options qui ne peuvent avoir lieu la même demi-journée sont reliées par une arête.
    Il peut s'agir du graphe

    d) Situation 4 :
    Les sommets d'un graphe représentent des nombres; deux nombres sont reliés par une arête si leurs écritures sur le dessin ci-dessous se chevauchent (même très légèrement!)

    Il peut s'agir du graphe


    6) Des ponts et des promenades...
    a) Dans la Ville aux Huit Ponts (ci-dessous)...

    ...est-il possible de se promener en passant par tous les ponts une fois et une seule et de revenir à son point de départ ?

    b) Ci-dessous, un plan de la ville de Königsberg (aujourd'hui Kaliningrad) où les quartiers sont reliés par 7 ponts.

    Est-il possible de se promener dans Königsberg en passant par chacun des 7 ponts une fois et une seule ?








    Fin de l'exercice de maths (mathématiques) Graphes: Chaîne eulérienne (niveau T ES) - cours
    Un exercice de maths gratuit pour apprendre les maths (mathématiques). (tags: probleme )
    Tous les exercices | Plus de cours et d'exercices de maths (mathématiques) sur le même thème: Calculs
    Recommander cette page En haut


    > 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

    > PARTENAIRES: Sites pour professeurs | Sites pour parents | Sites de professeurs | Cours mathématiques | Cours d'espagnol | Cours d'allemand | Cours de français | Cours de maths | Outils utiles | Bac d'anglais | Learn French | Learn English | Créez des exercices | Dernières recherches

    > 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 | Cours et exercices de mathématiques 100% gratuits, hors abonnement internet auprès d'un fournisseur d'accès.


    .