Projet algo des graphes
Utilisateur anonyme
-
Utilisateur anonyme -
Utilisateur anonyme -
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.
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.
A voir également:
- Projet algo des graphes
- Filigrane projet - Guide
- Gant projet - Télécharger - Gestion de projets
- Musique projet x ✓ - Forum Musique / Radio / Clip
- Musique du film Projet X - Forum Musique / Radio / Clip
- Différence entre pmo et chef de projet ✓ - Forum Programmation
10 réponses
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/
https://www.fichier-pdf.fr/2013/05/01/lex-bfs3-1/
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 !
Tu dis que le premier graphe (LEXBFS2.pdf) n'est pas triangulé alors qu'il l'est !
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é.
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é.
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é.
"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...
"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...
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
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.
https://www.fichier-pdf.fr/2013/05/01/lex-bfs-2/
J'ai aussi rectifié le tableau. Est-ce bon ?. Merci pour tout.
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...)
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...)
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é.
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.
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.
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.
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 ;-)
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.
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.
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.
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.
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.
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.