> 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 67910Je ne sais pas


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



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

a) L'ordre du graphe B est 97106Je ne sais pas


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



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 ? on ne peut pas savoirnonouiJe ne sais pas



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 ? on ne peut pas savoirnonouiJe ne sais pas



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 CDBAJe ne sais pas


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 CDBAJe ne sais pas


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 CBADJe ne sais pas


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 BCDAJe ne sais pas



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 ? nonon ne peut pas savoirouiJe ne sais pas


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 ? nonon ne peut pas savoirouiJe ne sais pas