graphe eulerien

[invite416c21c2]

bonjour jai voulais savoir comment tracer un graphe qui permet de faire des passage d'une et une seul foi sur chaque arrete dapres le theoreme d'euler
merci jatten le plus vite possible
-----

[invite2bd4953c]

Salut,

je ne comprends pas très bien ce que tu veux dire. S'agit-il de programmer quelque chose qui affiche des graphes eulériens sur l'écran d'un ordinateur ou souhaites-tu simplement en tracer à la main ?

[invite416c21c2]

OUI comme tu la dit j'ai voulais avoir un graphe que lorsque on affiche sur l'ecran qui repond au theoreme d'euler(le passage d'une et une seul foi sur chaque arrete c'est a dire un code qui es executable sur java j'ai doit rendre pour mon soutenance
merci encore

[invite986312212]

décider si un graphe est eulérien ou non est très simple, il suffit de vérifier la parité des degrés. Après le dessiner sur l'ordinateur de façon à produire un dessin agréable (par exemple sans croisements s'il est planaire) doit être plus difficile.

[A voir en vidéo sur Futura]

[invite2bd4953c]

En effet si il s'agit de tracer un graphe eulérien donné ce n'est pas très difficile (prend n'importe quel graphe connexe où tous les degrés sont pairs). Par contre si tu souhaites produire un algorithme qui étant donné un graphe en entrée, vérifie s'il est eulérien et produit un cycle eulérien en temps polynomial en la taille du graphe, ca prend un peu plus de temps mais ce n'est pas très difficile non plus (enfin cela dépend de la complexité souhaitée je suppose...). Regarde dans n'importe quel livre d'optimisation combinatoire un tant soit peu fourni (Korte-Vygen au hasard) et tu trouveras de quoi coder ton algorithme. Pour tracer le graphe c'est une autre histoire si tu veux que les arêtes ne se croisent qu'aux extrémités, et bien sûr ce n'est pas toujours possible même pour un graphe eulérien (K_5 par exemple).

[invite416c21c2]

alor vous me dite que c"est pas possible d'avoir un code en java qui permet de dessigner un grphe tout en appliquon le theoreme d 'euler ou vs me dit la ou jai peux recupere ces urgent
sino un code qui permet de dessigner un graphe seulement