Projet algo des graphes

[Fermé]
Signaler
Messages postés
170
Date d'inscription
mercredi 15 juillet 2009
Statut
Membre
Dernière intervention
28 mai 2015
-
Messages postés
170
Date d'inscription
mercredi 15 juillet 2009
Statut
Membre
Dernière intervention
28 mai 2015
-
Bonjour à tous,

Notre professeur vient de nous donner un projet d'algo des graphes et j'ai pas mal de difficultés dans cette matière.
En plus de ça, on n'a que très peu de temps et l'autre groupe de TD cela fait déjà 2 semaines qui ont eu le projet et ils ont eu les vacances.
J'ai deux autres projets en cours alors je suis un peu débordé.
J'ai un projet je dois terminer le rapport et c'est fini.
L'autre projet on n'a pas fait grand chose et ce projet des graphes on commence seulement.

La première question : nous devons exécuter les algorithmes Lex-BFS et MCS sur deux graphes différents (un triangulé, un autre non-triangulé).

J'ai fait mon premier graphe non triangulé, j'ai exécuté Lex-BFS et voilà ce que cela donne :
http://myreader.toile-libre.org/LEXBFS2.pdf

J'aimerais savoir si cela est correct s'il vous plaît et comment conclure qu'il n'est pas triangulé ?

Cordialement et merci beaucoup d'avance.

MODIFICATION : 01/05/2012 10h40m environ. Il y avait une erreur.

10 réponses

Messages postés
170
Date d'inscription
mercredi 15 juillet 2009
Statut
Membre
Dernière intervention
28 mai 2015
1
Ma camarade a fait le deuxième graphe. J'aimerai savoir si c'est bon ou pas s'il vous plaît. Ce graphe est censé être triangulé.

https://www.fichier-pdf.fr/2013/05/01/lex-bfs3-1/
Messages postés
16404
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
15 octobre 2021
2 896
Il va falloir revoir la définition d'un graphe triangulé (appelé aussi graphe cordal).

Tu dis que le premier graphe (LEXBFS2.pdf) n'est pas triangulé alors qu'il l'est !
Et tu dis que le deuxième graphe (Lex-BFS3.pdf) est triangulé, alors qu'il ne l'est pas !
Il y a encore du travail...
Messages postés
170
Date d'inscription
mercredi 15 juillet 2009
Statut
Membre
Dernière intervention
28 mai 2015
1
Le premier graphe n'est pas triangulé, vous faites une erreur.
Exemple sur le cycle a b i j h g f, il n'y a pas de corde et pourtant c'est un cycle de plus de 4 sommets.
Messages postés
170
Date d'inscription
mercredi 15 juillet 2009
Statut
Membre
Dernière intervention
28 mai 2015
1
Il y avait une erreur pour le deuxième graphe.
https://www.fichier-pdf.fr/2013/05/01/lex-bfs3-2/
Voilà la correction du deuxième graphe.
Et c'est le professeur qui m'a dit que le graphe 1 n'est pas triangulé et que le deuxième est triangulé.
Messages postés
16404
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
15 octobre 2021
2 896
Avec les modifications, ton deuxième graphe (lex-bfs3-2) ne ressemble plus du tout à celui de tout à l'heure ! Mais effectivement, maintenant il est triangulé.
Remarque : ce serait plus facile de le voir si tu représentait ton graphe planaire !

"c'est le professeur qui m'a dit que le graphe 1 n'est pas triangulé"
Pourtant il l'est ! Et c'est immédiat à voir, sans rien calculer...
Messages postés
170
Date d'inscription
mercredi 15 juillet 2009
Statut
Membre
Dernière intervention
28 mai 2015
1
Merci beaucoup. En faite on doit avoir 2 graphes, un triangulé et l'autre non. Est-ce que pour le premier graphe (LEXBFS2.pdf), si je retire certaines arêtes et que j'obtiens la figure suivante, est-ce bien un graphe non triangulé?
https://www.fichier-pdf.fr/2013/05/01/lex-bfs-2/

J'ai aussi rectifié le tableau. Est-ce bon ?. Merci pour tout.
Messages postés
16404
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
15 octobre 2021
2 896
En enlevant des cordes au cliques tu va forcément supprimer la triangularité du graphe.

Pour ce qui est de ton tableau, le résultat final doit être un ordonnancement d'élimination parfaite si le graphe est triangulé. Chez toi ça donne [h,j,g,d,i,e,f,c,b,a] mais "h" n'est pas simplicial (car {e,g,j} n'est pas une clique), donc le graphe n'est pas triangulé (ou ton tableau est faux...)
Messages postés
170
Date d'inscription
mercredi 15 juillet 2009
Statut
Membre
Dernière intervention
28 mai 2015
1
Merci
Messages postés
170
Date d'inscription
mercredi 15 juillet 2009
Statut
Membre
Dernière intervention
28 mai 2015
1
Je dois lancer l'algorithme sur un graphe triangulé et un autre qui ne l'est pas. Sur ce graphe j'ai enlevé des cordes de sorte qu'il ne soit plus triangulé.
Messages postés
16404
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
15 octobre 2021
2 896
J'ai bien compris.
Et d'après tes calculs on a bien le graphe qui doit être triangulé qui est déterminé comme triangulé, et le graphe que tu as modifié pour ne pas être triangulé est bien déterminé comme étant non triangulé.

Cependant je n'ai pas vérifié les calculs. Ce n'est pas parce que tu arrives à la bonne conclusion que la démarche est correcte.
Messages postés
170
Date d'inscription
mercredi 15 juillet 2009
Statut
Membre
Dernière intervention
28 mai 2015
1
Merci :)
Messages postés
170
Date d'inscription
mercredi 15 juillet 2009
Statut
Membre
Dernière intervention
28 mai 2015
1
Je sais, c'est pour cela que je demande si cela est juste ou non car en général on ne voit pas ses propres erreurs.
Messages postés
16404
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
15 octobre 2021
2 896
Le problème c'est que je ne comprends pas ton tableau, j'imagine que c'est comme ça qu'on t'as appris à faire, mais moi je ne peux pas le relire pour le vérifier. J'ai compris le résultat de la dernière ligne pour en déduire l'ordonnancement, et donc arriver aux conclusions que je t'ai donné, mais pour la démarche je ne peux pas t'aider à la contrôler. Mais arriver à la bonne conclusion est quand même un bon indicateur de réussite ;-)
Messages postés
170
Date d'inscription
mercredi 15 juillet 2009
Statut
Membre
Dernière intervention
28 mai 2015
1
D'accord. Merci beaucoup KX
Messages postés
170
Date d'inscription
mercredi 15 juillet 2009
Statut
Membre
Dernière intervention
28 mai 2015
1
Bonjour KX,

Qu'est-ce qui vous coince pour l'exécution ?

Ma camarade a fait l'exécution de l'algorithme MCS.

https://www.fichier-pdf.fr/2013/05/02/lex-bfs3-autrealgo/
et
https://www.fichier-pdf.fr/2013/05/02/e/

Pouvez-vous regarder si c'est bon s'il vous plaît ? Surtout que celui-là est plus dur à comprendre car il parle de label(x), ?(i) et on ne sait pas vraiment la structure de données utilisée car rien n'est dit. Et pour cette algo on n'a pas d'exemple.

Merci beaucoup d'avance.
Messages postés
170
Date d'inscription
mercredi 15 juillet 2009
Statut
Membre
Dernière intervention
28 mai 2015
1
Bonjour,

J'ai calculé la complexité approximative des deux algorithme et j'aimerai savoir si c'est correct. Merci beaucoup d'avance.


Les deux algorithmes sont similaires, ils auront donc la même complexité.

Dans le cas d'une matrice, l'initialisation par ? coûte n. Pour ce qui est de la suite, soit on considère que le choix du sommet non numéroté de label maximum coûtera 1 (si jamais c'est trié), soit on considère qu'il faut tout parcourir ce qui coûtera n. Dans les deux cas, nous sommes dans une matrice donc à l'étape suivante (qui consiste à consulter les voisins de x) coûtera n puisque pour trouver tous les sommets adjacents à x nous devrons parcourir la ligne complète. Conclusion : la complexité est de ?(n²)

Dans le cas d'un tableau de listes de successeurs, l'initialisation coûtera la même chose. Pour le choix du label maximum, cela dépend aussi si c'est trié ou non. En revanche, là où il y a un gain de complexité c'est pour rechercher les voisins de x. Si le choix du label maximum est considéré comme coûtant n, la complexité restera de l'ordre de ?(n²), sinon, elle sera de l'ordre de ?(n*successeurs(x)).


Cordialement et merci beaucoup.
Messages postés
170
Date d'inscription
mercredi 15 juillet 2009
Statut
Membre
Dernière intervention
28 mai 2015
1
Bonjour à tous,

J'essaie de faire la suite mais je reste bloqué, je ne comprends pas la question surtout.


Théorème 3 - Soit G=(S,A) un graphe triangulé et ro = [x1....xn] un shéma d'élimination parfait de G. Soit H=(S,F) un graphe orienté obtenu en orientant les arêtes de G de la façon suivante: (x,y) appartenant à F ssi {x,y} appartenant A et x est avant y dans ro. Alors :
1- G est un graphe sans circuit.
2-Tout tri topo t sur H est un shéma d'élimination parfait

- Proposer un algorithme qu'on appellera "triangulé-tri-topologique" qui trouve le graphe H et un tri topologique t sur H d'un graphe triangulé G conformément au théorème 3 ci-dessus. Calculer la complexité théorique de votre algorithme dans le pire des cas en fonction des structures de données.

Je dois faire un tri topologique si je comprends bien ????

Cordialement et merci beaucoup d'avance.