Cours de mathématiques gratuitsCréer un test
Connectez-vous !

Cliquez ici pour vous connecter
Nouveau compte
Des millions de comptes créés sur nos sites

100% gratuit !
[Avantages]


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

Recommandés :
- 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 & d'exercices de maths (mathématiques) sur le même thème : Problèmes [Autres thèmes]
> Tests similaires : - 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 - Test de niveau(9)- Situations Problèmes 3 (CM2/6ème) - Problèmes : Vitesse /Durée/ Distance parcourue - Test de niveau (4)- Logique (Fin de cycle 2 des apprentissages fondamentaux) - Suites numériques
> 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é de cinq sommets et de six arêtes; c'est un graphe d'ordre 5.

Un graphe est une structure très simple constituée 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é Tweeter Partager
Exercice de maths (mathématiques) "Graphes: Chaîne eulérienne (niveau T ES) - 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) 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 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).
Tous les exercices | Plus de cours et d'exercices de maths (mathématiques) sur le même thème : Problèmes



 


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

> NOS AUTRES SITES GRATUITS : Cours d'anglais | Cours de français | Cours d'espagnol | Cours d'italien | Cours d'allemand | Cours de néerlandais | Tests de culture générale | Cours de japonais | Rapidité au clavier | Cours de latin | Cours de provençal | Moteur de recherche sites éducatifs | Outils utiles | Bac d'anglais | Our sites in English

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



| Partager sur les réseaux