Pour aborder ces problèmes il faut partir d'un peu de théorie...
1. On appelle degré d'un sommet d'un graphe (non orienté) le nombre d'arêtes partant de ce graphe.
2 une chaine eulérienne est une chaine passant une et une seule fois par toutes les arêtes du graphe.
3 un cycle eulérien est une chaine eulérienne dont le sommet de départ et le sommet d'arrivée sont identiques.
4 Un graphe connexe possède une chaine eulérienne si et seulement si ses sommets sont tous de degré pair sauf au plus deux.
5 Un graphe connexe possède un cycle eulérien si et seulement si tous ses sommets sont de degré pair.
Le premier graphe possède 3 sommets de degré pair (dans ce cas là de degré 2) et 2 somment de degré impaire (deg 3) Donc ce graphe peut être parcouru en ne passant qu'une seule fois sur chaque arête.
Le deuxième graphe possède tous ces sommets de degré impaire, donc, on ne peut pas tracer le graphe sans lever le crayon.
Le troisième graphe possède 3 sommets de degré pair (1 de degré 2 et 2 de degré 4) et 2 sommets de degré impaire (degré 3). Donc ce graphe peut être parcouru en ne passant qu'une seule fois sur chaque arête.
Pour aborder ces problèmes il faut partir d'un peu de théorie...
RépondreSupprimer1. On appelle degré d'un sommet d'un graphe (non orienté) le nombre d'arêtes partant de ce graphe.
2 une chaine eulérienne est une chaine passant une et une seule fois par toutes les arêtes du graphe.
3 un cycle eulérien est une chaine eulérienne dont le sommet de départ et le sommet d'arrivée sont identiques.
4 Un graphe connexe possède une chaine eulérienne si et seulement si ses sommets sont tous de degré pair sauf au plus deux.
5 Un graphe connexe possède un cycle eulérien si et seulement si tous ses sommets sont de degré pair.
Le premier graphe possède 3 sommets de degré pair (dans ce cas là de degré 2) et 2 somment de degré impaire (deg 3)
Donc ce graphe peut être parcouru en ne passant qu'une seule fois sur chaque arête.
Le deuxième graphe possède tous ces sommets de degré impaire, donc, on ne peut pas tracer le graphe sans lever le crayon.
Le troisième graphe possède 3 sommets de degré pair (1 de degré 2 et 2 de degré 4) et 2 sommets de degré impaire (degré 3).
Donc ce graphe peut être parcouru en ne passant qu'une seule fois sur chaque arête.
en effet, et on commencera la chaîne à partir d'un sommet de degré impair pour la finir par l'autre sommet de degré impair
RépondreSupprimer