Théorème d'Euler, graphes orientés

par **Omc** » 14 Déc 2007, 18:07

Qui connaît l'énoncé EXACT du théorème d'Euler pour les graphes ORIENTES ?C'est de la spé de TES

Merci d'avance

O.

par **rene38** » 14 Déc 2007, 18:11

BONJOUR ?

Tu peux regarder [url="http://fr.wikipedia.org/wiki/Graphe_eul%C3%A9rien"]ici[/url].

par **ghghgh** » 14 Déc 2007, 21:14

c'est intéressant l'étude des graphes en tes ?
c'est dommage qu'on en ait pas en S...

par **lapras** » 15 Déc 2007, 07:33

Bien d'accord. Tu sais que les graphes sont au programme des olympiades ?

par **Omc** » 17 Déc 2007, 09:48

rene38 a écrit:BONJOUR ?

Tu peux regarder [url="http://fr.wikipedia.org/wiki/Graphe_eul%C3%A9rien"]ici[/url].

Merci !

Dans l'article de Wiki, ils parlent de circuit alors que notre prof parle de cycle. Ils ne traitent que de parcours dans un graphe (tous les sommets de degré pair) et pas de chaînes (partant d'un sommet et allant vers un autre sommet). Dans ce cas d'après notre prof tous les sommets sont pairs sauf le sommet du début de la chaîne et le sommet de la fin. Pour les graphes orientés l'article parle de cycles mais pas de chaînes. Est-ce qu'il y a un énoncé du théorème d'Euler dans ce cas-là ?

O.

par **Dominique Lefebvre** » 17 Déc 2007, 10:21

Omc a écrit:Merci !

Dans l'article de Wiki, ils parlent de circuit alors que notre prof parle de cycle. Ils ne traitent que de parcours dans un graphe (tous les sommets de degré pair) et pas de chaînes (partant d'un sommet et allant vers un autre sommet). Dans ce cas d'après notre prof tous les sommets sont pairs sauf le sommet du début de la chaîne et le sommet de la fin. Pour les graphes orientés l'article parle de cycles mais pas de chaînes. Est-ce qu'il y a un énoncé du théorème d'Euler dans ce cas-là ?

O.

Ce document traite du cas des chaînes et des cycles [url="http://www.math.u-bordeaux.fr/~coulange/capes/graphesac.pdf"]http://www.math.u-bordeaux.fr/~coulange/capes/graphesac.pdf[/url]

par **SimonB** » 17 Déc 2007, 14:02

lapras a écrit:Bien d'accord. Tu sais que les graphes sont au programme des olympiades ?

Et si vous vous apprêtez à aller en prépa, vous n'en aurez pas non plus, des graphes (_sauf_ si vous passez l'épreuve d'informatique des ENS ; mais ça ne figure dans aucun programme). C'est dommage, parce que c'est joli et ça permet de démontrer de très jolies choses mathématiques qui n'ont rien à voir.

par **Omc** » 20 Déc 2007, 07:49

Dominique Lefebvre a écrit:Ce document traite du cas des chaînes et des cycles [url="http://www.math.u-bordeaux.fr/~coulange/capes/graphesac.pdf"]http://www.math.u-bordeaux.fr/~coulange/capes/graphesac.pdf[/url]

Merci Modérateur !

Mais votre document ne répond pas à ma question... Tant pis. Peut-être qu'il n'y a pas de théorème d'Euler pour les graphes orientés.

par **baryton** » 20 Déc 2007, 08:44

salut

trouvé sur internet:

Théorème d'Euler (version orientée) Un graphe orienté fortement connexe est Eulérien si et seulement si chacun de ses sommets est l'extrémité initiale et terminale du même nombre d'arêtes.

@+

par **Omc** » 21 Déc 2007, 18:52

baryton a écrit:salut

trouvé sur internet:

Théorème d'Euler (version orientée) Un graphe orienté fortement connexe est Eulérien si et seulement si chacun de ses sommets est l'extrémité initiale et terminale du même nombre d'arêtes.

@+

Je prends le graphe orienté suivant :
Sommets : 1,2,3,4,5
Arêtes : 1>2, 2>3, 3>4, 5>6, 6>1, 1>3, 2>5, 3>5, 4>1, 6>2

Il est fortement connexe
Il est eulérien (il existe une chaîne orientée eulérienne partant de 6 et aboutissant à 5)

Mais :
De 6, il part une arête de plus qu'il n'en arrive
A 5, il arrive une arête de plus qu'il n'en part

:happy2:

Théorème d'Euler, graphes orientés

Théorème d'Euler, graphes orientés

Qui est en ligne