Théorie des graphes 2

[virginie66]

bonjour à tous

je vous écris ce message car j'ai des difficultés à résoudre trois problèmes en théorie des graphes. Voici les énoncés :

Ajouter les instructions convenables dans l'algorithme de parcours en profondeur d'abord, afin d'afficher toutes les permutations de l'ensemble {1,2...n}
indication: appliquer le parcours sur le graphe complet de N sommets

Effectuer l'algorithme approché du problème de voyageur de commerce sur le graphe complet de 5 sommets. le poids de l'arête ij est i*j+1 ( i plus petit que j)

Considérons un graphe G eulérien ( un graphe connexe avec le degré de chaque sommet pair) Montrer que G ne possède pas une coupe de cardinalité impair
Une coupe est un ensemble d'arêtes minimal (minimal par rapport à l'inclusion) dont la suppression disconnecte le graphe
utilisons le théorème d'Euler

voilà
est ce que vous pouvez m'aider s'il vous plait ?

[virginie66]

s'il vous plait aidez moi c'est vraiment important
merci

[fatal_error]

salut,

Ajouter les instructions convenables dans l'algorithme de parcours en profondeur d'abord, afin d'afficher toutes les permutations de l'ensemble {1,2...n}
indication: appliquer le parcours sur le graphe complet de N sommets

tu prends N sommets, numérotés de 1 à n.
Tu les interconnectes tous (1 pointe vers 2 a n, 2 pointe vers 1 et 3 a n, etc)

Tu met un ptit parametre de récursivité. que t'incrémentes a chaque fois que tu te rappèles.
Lorsque t'arrives au niveau n, alors t'as une perm complete.

Faut appliquer lalgo au début sur le sommet 1, puis le refaire sur le sommet 2, etc...
Pour le reste j'en sais rien