Aller au contenu

Exercice SPE maths_Graphe


Ashe08

Messages recommandés

Bonjour,

je créai ce nouveau sujet car je suis bloquée dans cet exercice.

Je ne sais pas comment donner la justification à la question 2 et je ne sais comment répondre à la question 3 où il est demandé si le graphe est Eulerien ou Hamiltonien.

Merci d'avance pour votre aide.

Voici l'énoncé de l'exercice:

IMG_20190311_115110.thumb.jpg.54dac94f15e4b09a3989c3249b0c8a37.jpg

IMG_20190311_115120.thumb.jpg.164353e95aca846475036a842d8dfefb.jpg

 

Et voici ce que j'ai déjà fait :

IMG_20190311_122616.thumb.jpg.c5a5e31a78bf1e08ed95050f1e3e445d.jpg

Lien vers le commentaire
Partager sur d’autres sites

  • E-Bahut

2-Graphes planaires car ils peuvent être représentés sans que aucune de leurs arrêtes se croisent.

3a- G1 est Eulérien (deux sommets d’ordre impair) car possédant une chaîne Eulérienne et pas Hamiltonien car sommet d'ordre 1

1.jpeg.b17c2714e8ec58258a18d9a1c0b39880.jpeg

3b- G2 est Eulérien (tous les sommets sont pairs) et Hamiltonien car possédant au moins un cycle  Hamiltonien

2.jpeg.da49e78d07ac44e198a2294841305d71.jpeg

3b- G3 n’est pas Eulérien  ( plus de deux sommets d’ordre impair) et Hamiltonien car possédant au moins un cycle  Hamiltonien

3.jpeg

Lien vers le commentaire
Partager sur d’autres sites

  • E-Bahut

Je suis allé revoir les définitions et il se trouve que je les avais un peu oubliéees... alors il faut corriger ce que j'ai écrit (j'ai mélangé  cycle eulérien et chaîne) 

Un graphe eulérien est un graphe qui possède un cycle eulérien. Un cycle eulérien est un cycle qui passe une fois et une seule par chaque arête du graphe. Une chaîne eulérienne est une chaîne qui contient une fois et une seule chaque arête du graphe. Un graphe connexe admet une chaîne eulérienne si et seulement si le nombre de sommets de degré impair est 0 ou 2. 

Un graphe hamiltonien est un graphe qui possède un cycle hamiltonien.  Un cycle hamiltonien est un cycle qui passe une fois et une seule par chaque sommet du graphe.  

 

--------------------------

- Le graphe 1 n'est ni eulérien (bien qu'il possède une chaine eulérienne (2 sommet impairs) mais ce n'est pas un cycle) ni hamiltonien (pas de cycle hamiltonien)

1.jpeg.d4c01fb35029ccb6ab1c3dded23c195d.jpeg

- Le graphe  2 est  Eulérien et Hamiltonien car il possède un cycle éulérien et hamiltonien

2.jpeg.3eeaf9319791f703de9c43b5604564f2.jpeg

- Le graphe  3 n'est  pas eulérien (pas de chaine eulérienne car plus de 2 sommets impairs donc pas de cycle eulérien) .Il est Hamiltonien car il possède au moins  un cycle hamiltonien

3.jpeg.f6fafd6b0457f0bf0ca9b607c0b40224.jpeg

Lien vers le commentaire
Partager sur d’autres sites

Archivé

Ce sujet est désormais archivé et ne peut plus recevoir de nouvelles réponses.

×
×
  • Créer...
spam filtering
spam filtering