Projet algo des graphes Fermé

Question

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.

Utilisateur anonyme · Answer

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/

KX · Answer

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...

Utilisateur anonyme · Answer

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é.

KX · Answer

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...

Utilisateur anonyme · Answer

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.

Utilisateur anonyme · Answer

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é.

Utilisateur anonyme · Answer

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.

Utilisateur anonyme · Answer

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.

Utilisateur anonyme · Answer

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.

Utilisateur anonyme · Answer

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.

Projet algo des graphes

10 réponses

Discussions similaires