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é 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 (1) (niveau Terminale ES)' créé le 14-06-2008 par iza51 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)


1) On considère le graphe A ci-dessous :

a) L'ordre du graphe A est 91067

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


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

a) L'ordre du graphe B est 97106

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


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


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


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 DBAC

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 DABC

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 ACDB

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 BDAC


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 ? nonouion ne peut pas savoir

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 savoiroui