Utiliser le théorème dEuler en situation PDF

Introduction à la théorie des graphes

Théorème d'Euler (1766). Un graphe simple connexe G = (X A) est eulérien si et seulement si pour tout sommet x de X

GRAPHES (Partie 1)

Vidéo https://youtu.be/gznmzmzjBsQ. 1) Un hectogone est un polygone à D'après le théorème d'Euler le graphe étant connexe

Cours Théorie des graphes Pierre Bornsztein Table des matières

2 août 2003 Théorème 4 (Formule d'Euler 1758). Soit G un graphe simple planaire connexe dont une représentation planaire possède s som-.

Théorème dEuler Soit G un graphe simple planaire connexe. Soit s

Démonstration: Regardons tout d'abord un cas particulier extrêmement simple : le graphe qui a un seul sommet et pas d'arête

INF303 Modélisation des structures informatiques : applications

Théorème (formule d'Euler). Soit G un graphe connexe plongé dans le plan avec n

A propos du théorème dEuler et des parcours eulériens dans les

recherche de parcours eulérien dans un graphe et la pertinence de ce démonstration

Utiliser le théorème dEuler en situation

Dans la ville de Graphe on s'intéresse aux principales rues permettant de relier différents lieux ou- verts au public

Théorie des graphes

Théorème d'Euler. Ici G est un graphe dont l'ensemble des sommets est : { A B

Les Classiques de la Théorie des Graphes (Première partie)

12 avr. 2013 Théorème (Euler 1736). Un graphe connexe G est eulérien si et seulement si chacun de ses noeuds a un degré pair.

Théorie des graphes Université de La Rochelle Frédéric TESTARD

Démonstration – (a) Dans cette somme chaque arête est comptée deux fois

Algorithme d"EulerGraphes non orientés2012-2013

Spécialité Mathématiques

Term ES

D"après Bac ES Asie 2003

Utiliser le théorème d"Euler en situation

Dans la ville de Graphe, on s"intéresse aux principales rues permettant de relier différents lieux ou-

verts au public, à savoir la mairie (M), le centre commercial (C), la bibliothèque (B), la piscine (P)

et le lycée (L). Chacun de ces lieux est désigné par son initiale. Le tableau ci-dessous donne les rues

existant entre ces lieux.BCLMP

B×××

C×××

L××

M××××

P××

1. Dessiner un graphe G représen tantcette situation.

Solution:Les sommets du graphe sont les différents lieux de la ville et les arêtes les différentes

rues existantes entre ces lieux.2.Mon trerqu"il est p ossiblede trouv erun tra jetempru ntantune fois et une seule toutes les rues de

ce plan. Justifier. Proposer un tel trajet.

Solution:Le problème posé revient à chercher dans le graphe G une chaîne eulérienne ou un

cycle eulérien. Le graphe G est connexe : deux sommets quelconques du graphe peuvent toujours être reliés par une chaîne. On donne ci-dessous le tableau des degrés des sommets du graphes.SommetBCLMP

Degré33242

Géraldine MénéxiadisPage 1 / 2

Algorithme d"EulerGraphes non orientés2012-2013

Spécialité Mathématiques

Term ES

Le nombre de sommets de degré impair est 2 :ce sont les sommets B et C.

D"après le théorème d"Euler, le graphe G admet donc une chaîne eulérienne. Les extrémités

de la chaîne sont les sommets de degré impair, soit B et C. Pour déterminer une telle chaîne, on applique l"algorithme du cours et on trouve par exemple, par étapes successives : Étape 1 :B-P-M-L-C (recherche d"une chaîne d"extrémités B et C) Étape 2 :on insère le cycle B-M-C-B à la place de B dans la chaîne précédente. On obtient B-M-C-B à la place de B dans la chaîne précédente.

On obtient B-M-C-B-P-M-L-C.

Étape 3 :toutes les arêtes du graphe ont été utilisées; une chaîne eulérienne possible estB-M-C-B-P-M-L-C. Conclusion :d"après ce qui précède, il est possible de trouver un trajet qui emprunte une

fois et une seule toutes les rues. Ce chemin possible estB-M-C-B-P-M-L-C.3.Est-il p ossibled"a voirun tra jetpartan tet arriv antdu même lieu et passan tune fois et une seule

par toutes les rues? Solution:La question posée, retraduite en termes de graphe est : le graphe G admet-il un cycle eulérien?

D"après ce qui précède, G est connexe et tous ses sommets ne sont pas de degré pair donc,

d"après le théorème d"Euler, le graphe G n"admet pas de cycle eulérien. Conclusion :il n"est pas possible d"avoir un trajet partant et arrivant du même lieu et passant une fois et une seule par toutes les rues.Méthode

1.Bien repérer les éléments du texte qui seront matérialisés par les sommets du graphe et ceux qui

seront matérialisés par les arêtes.

2.et3.Il faut tout d"abord traduire la question avec le vocabulaire des graphes. Il faut ensuite

préciser la connexité du graphe utilisé et dresser le tableau des degrés des sommets, afin de pouvoir

identifier la conclusion à donner à l"aide du théorème d"Euler.

Géraldine Ménéxiadis

Page 2 / 2

quotesdbs_dbs50.pdfusesText_50

[PDF] Utiliser le théorème dEuler en situation

Spécialité Mathématiques

Term ES

D"après Bac ES Asie 2003

Utiliser le théorème d"Euler en situation

B×××

C×××

L××

M××××

P××

Degré33242

Géraldine MénéxiadisPage 1 / 2

Spécialité Mathématiques

Term ES

On obtient B-M-C-B-P-M-L-C.

1.Bien repérer les éléments du texte qui seront matérialisés par les sommets du graphe et ceux qui

2.et3.Il faut tout d"abord traduire la question avec le vocabulaire des graphes. Il faut ensuite

Géraldine Ménéxiadis

Page 2 / 2