Projet algo des graphes
Fermé
Utilisateur anonyme
-
Modifié par Etienne256 le 1/05/2013 à 10:40
Utilisateur anonyme - 21 mai 2013 à 16:12
Utilisateur anonyme - 21 mai 2013 à 16:12
A voir également:
- Projet algo des graphes
- Gantt projet - Télécharger - Gestion de projets
- Musique projet x - Forum Musique / Radio / Clip
- Projet vba exemple ✓ - Forum VB / VBA
- Projet de creation d'une chaine de television pdf - Forum TV & Vidéo
- Film projet x a telecharger gratuitement - Télécharger - Outils professionnels
10 réponses
Utilisateur anonyme
Modifié par Etienne256 le 1/05/2013 à 15:33
Modifié par Etienne256 le 1/05/2013 à 15:33
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/
KX
Messages postés
16733
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 janvier 2024
3 015
1 mai 2013 à 15:41
1 mai 2013 à 15:41
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 !
Utilisateur anonyme
1 mai 2013 à 16:00
1 mai 2013 à 16:00
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é.
KX
Messages postés
16733
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 janvier 2024
3 015
1 mai 2013 à 16:30
1 mai 2013 à 16:30
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
Utilisateur anonyme
Modifié par Etienne256 le 1/05/2013 à 17:21
Modifié par Etienne256 le 1/05/2013 à 17:21
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.
KX
Messages postés
16733
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 janvier 2024
3 015
1 mai 2013 à 18:26
1 mai 2013 à 18:26
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...)
Utilisateur anonyme
1 mai 2013 à 19:40
1 mai 2013 à 19:40
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é.
KX
Messages postés
16733
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 janvier 2024
3 015
1 mai 2013 à 19:48
1 mai 2013 à 19:48
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.
Utilisateur anonyme
1 mai 2013 à 20:08
1 mai 2013 à 20:08
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.
KX
Messages postés
16733
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 janvier 2024
3 015
1 mai 2013 à 20:20
1 mai 2013 à 20:20
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 ;-)
Utilisateur anonyme
Modifié par Etienne256 le 2/05/2013 à 08:44
Modifié par Etienne256 le 2/05/2013 à 08:44
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.
Utilisateur anonyme
Modifié par Etienne256 le 4/05/2013 à 17:39
Modifié par Etienne256 le 4/05/2013 à 17:39
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.
Utilisateur anonyme
5 mai 2013 à 11:27
5 mai 2013 à 11:27
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.
