Algorithmique sur les graphes
Résolu/Fermé
hamid_touroug
Messages postés
13
Date d'inscription
dimanche 20 mai 2007
Statut
Membre
Dernière intervention
7 avril 2008
-
25 juil. 2007 à 18:01
mamiemando Messages postés 33129 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 27 mai 2024 - 16 févr. 2009 à 15:31
mamiemando Messages postés 33129 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 27 mai 2024 - 16 févr. 2009 à 15:31
A voir également:
- Algorithmique sur les graphes
- Comment faire x3 sur une calculatrice casio graph 25+e ✓ - Forum calculatrices
- Comment faire x sur une calculatrice casio graph 35+e - Forum calculatrices
- Comment faire un graphe sur excel - Guide
- Comment faire la racine carré sur calculatrice casio graph 25+e - Forum calculatrices
- Comment résoudre un problème algorithmique - Forum Pascal
11 réponses
mamiemando
Messages postés
33129
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
27 mai 2024
7 755
25 juil. 2007 à 18:18
25 juil. 2007 à 18:18
Réponses
Se déplacer de n'importe quel carrefour à n'importe quel autre-->Graphe connexe.
1) Dans un graphe non orienté oui. Vu que le graphe est orienté on parlerait de graphe fortement connexe (pour tout u,v il existe un chemin orienté de u à v et de v à u). Tu peux aussi voir ça en terme de fermeture transitive (la fermeture transitive est une clique)
https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/strong_components.html#def:strongly-connected-component
Lorsqu'une rue devient critique, le graphe perd sa connexité.
2) sa forte connexité.
Rue en double sens-->utilisation des arêtes.
Rue en sens unique-->Utilisation des arcs. (On a donc besoin d'un algorithme qui convertit un graphs non-orienté en un graphe orienté)
3) En terme d'implémentation il est beaucoup plus simple de travailler tout le temps avec des arcs orientés quitte à a voir un arc (u,v) et un arc (v,u).
Pour l'implémentation du graphe,quelle représentation doit-on utiliser? représentation par liste ou par matrice?est ce que ce choix dépend de l'algorithme qui résoud ce probème?
4) Ca dépend. Des vecteurs (O(1)) te permettront d'avoir un algorithme beaucoup plus rapide que des listes (O(n)) ou des arbres O(log(n)). Il faut donc si le graphe n'est pas trop gros plutôt s'orienter vers des vecteurs.
Sous linux (ou cygwin)
Boost permet très facilement de changer la structure de ton graphe, mais ça suppose que tu codes en C++ et que tu installes la librairie boost (gratuite), du moins la boost graph library (BGL). Pour cela installe le paquet libboost-graph-dev (pour les debian et les ubuntu). En root (ou précédé d'un sudo) :
A noter que l'algorithme de strong components, comme tu as pu le voir dans le lien précédent est déjà codé dans la BGL. Récupère ces deux fichiers :
https://www.boost.org/doc/libs/1_72_0/libs/graph/example/strong_components.cpp
http://www.boost.org/libs/graph/example/scc.dot
Pour visualiser le graphe scc.dot, installe graphviz. En root (ou précédé d'un sudo) :
Ensuite il ne reste plus qu'à convertir le fichier .dot en image, par exemple avec dot, neato, fdp...
Pour compiler et exécuter l'exemple sous linux :
Bonne chance
Se déplacer de n'importe quel carrefour à n'importe quel autre-->Graphe connexe.
1) Dans un graphe non orienté oui. Vu que le graphe est orienté on parlerait de graphe fortement connexe (pour tout u,v il existe un chemin orienté de u à v et de v à u). Tu peux aussi voir ça en terme de fermeture transitive (la fermeture transitive est une clique)
https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/strong_components.html#def:strongly-connected-component
Lorsqu'une rue devient critique, le graphe perd sa connexité.
2) sa forte connexité.
Rue en double sens-->utilisation des arêtes.
Rue en sens unique-->Utilisation des arcs. (On a donc besoin d'un algorithme qui convertit un graphs non-orienté en un graphe orienté)
3) En terme d'implémentation il est beaucoup plus simple de travailler tout le temps avec des arcs orientés quitte à a voir un arc (u,v) et un arc (v,u).
Pour l'implémentation du graphe,quelle représentation doit-on utiliser? représentation par liste ou par matrice?est ce que ce choix dépend de l'algorithme qui résoud ce probème?
4) Ca dépend. Des vecteurs (O(1)) te permettront d'avoir un algorithme beaucoup plus rapide que des listes (O(n)) ou des arbres O(log(n)). Il faut donc si le graphe n'est pas trop gros plutôt s'orienter vers des vecteurs.
Sous linux (ou cygwin)
Boost permet très facilement de changer la structure de ton graphe, mais ça suppose que tu codes en C++ et que tu installes la librairie boost (gratuite), du moins la boost graph library (BGL). Pour cela installe le paquet libboost-graph-dev (pour les debian et les ubuntu). En root (ou précédé d'un sudo) :
(root@aldur) (~) # aptitude install libboost-graph-dev
A noter que l'algorithme de strong components, comme tu as pu le voir dans le lien précédent est déjà codé dans la BGL. Récupère ces deux fichiers :
https://www.boost.org/doc/libs/1_72_0/libs/graph/example/strong_components.cpp
http://www.boost.org/libs/graph/example/scc.dot
Pour visualiser le graphe scc.dot, installe graphviz. En root (ou précédé d'un sudo) :
(root@aldur) (~) # aptitude install graphviz
Ensuite il ne reste plus qu'à convertir le fichier .dot en image, par exemple avec dot, neato, fdp...
(mando@aldur) (~) $ dot scc.dot -Tgif -o scc.gif
Pour compiler et exécuter l'exemple sous linux :
(mando@aldur) (~) $ g++ -I/usr/include/boost/ -lbgl-viz strong_components.cpp (mando@aldur) (~) $ ./a.out A directed graph: a --> b f h b --> c a c --> d b d --> e e --> d f --> g g --> f d h --> i i --> h j e c j --> Total number of components: 4 Vertex a is in component 3 Vertex b is in component 3 Vertex c is in component 3 Vertex d is in component 0 Vertex e is in component 0 Vertex f is in component 1 Vertex g is in component 1 Vertex h is in component 3 Vertex i is in component 3 Vertex j is in component 2
Bonne chance
hamid_touroug
Messages postés
13
Date d'inscription
dimanche 20 mai 2007
Statut
Membre
Dernière intervention
7 avril 2008
28 juil. 2007 à 14:34
28 juil. 2007 à 14:34
Merci beaucoup mamiemando
bonne vacances
bonne vacances
mamiemando
Messages postés
33129
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
27 mai 2024
7 755
29 juil. 2007 à 19:25
29 juil. 2007 à 19:25
De même, bon courage ;)
hamid_touroug
Messages postés
13
Date d'inscription
dimanche 20 mai 2007
Statut
Membre
Dernière intervention
7 avril 2008
31 juil. 2007 à 01:24
31 juil. 2007 à 01:24
bonjour
dans votre premier message vous avez dis que le graphe est orienté mais je crois que ce n'est pas le cas car dans l'enoncé on précise que les rues sont à double sens donc il n'est pas orienté...c'est àça non??
dans votre premier message vous avez dis que le graphe est orienté mais je crois que ce n'est pas le cas car dans l'enoncé on précise que les rues sont à double sens donc il n'est pas orienté...c'est àça non??
mamiemando
Messages postés
33129
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
27 mai 2024
7 755
31 juil. 2007 à 10:03
31 juil. 2007 à 10:03
Non. Une rue en sens unique du carrefour u au carrefour v : un arc u->v, pas d'arc v->u.
Une rue dans les deux sens de u à v et de v à u : un arc u->v et un arc v->u.
Donc il est bien orienté ;)
Une rue dans les deux sens de u à v et de v à u : un arc u->v et un arc v->u.
Donc il est bien orienté ;)
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
hamid_touroug
Messages postés
13
Date d'inscription
dimanche 20 mai 2007
Statut
Membre
Dernière intervention
7 avril 2008
5 août 2007 à 11:44
5 août 2007 à 11:44
Ah ok dacor j'ai compris et merci pour tout.
hamid_touroug
Messages postés
13
Date d'inscription
dimanche 20 mai 2007
Statut
Membre
Dernière intervention
7 avril 2008
8 août 2007 à 02:26
8 août 2007 à 02:26
je cherche des exercices corrigés sur le cour "d'algorithmique des graphes" svp c'est trés urgent.
cordialement
cordialement
mamiemando
Messages postés
33129
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
27 mai 2024
7 755
8 août 2007 à 09:43
8 août 2007 à 09:43
http://www.apprendre-en-ligne.net/graphes/
Si ça ne te convient pas fais une recherche sur google.
Bonne chance
Si ça ne te convient pas fais une recherche sur google.
Bonne chance
hamid_touroug
Messages postés
13
Date d'inscription
dimanche 20 mai 2007
Statut
Membre
Dernière intervention
7 avril 2008
10 août 2007 à 01:09
10 août 2007 à 01:09
D'accord,
sinon vous auriez quelque chose à me proposer sur la k-coloriablité des graphes (j'ai deja cherché sur l net)
Merci
sinon vous auriez quelque chose à me proposer sur la k-coloriablité des graphes (j'ai deja cherché sur l net)
Merci
mamiemando
Messages postés
33129
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
27 mai 2024
7 755
10 août 2007 à 02:37
10 août 2007 à 02:37
Pourtant tu as l'embarras du choix
https://www.google.com/search?q=exercice+nombre+chromatique&ie=utf-8&oe=utf-8&aq=t&rls=org.debian:fr:unofficial&client=iceweasel-a&gws_rd=ssl
De toute façon qu'attends-tu de moi, à part faire une recherche google à ta place je ne vais pas t'apporter grand chose :s
Bonne chance
https://www.google.com/search?q=exercice+nombre+chromatique&ie=utf-8&oe=utf-8&aq=t&rls=org.debian:fr:unofficial&client=iceweasel-a&gws_rd=ssl
De toute façon qu'attends-tu de moi, à part faire une recherche google à ta place je ne vais pas t'apporter grand chose :s
Bonne chance
Bonjour,
je chercher a installer la lib graph Boost sous Cygwin, mais pas moyen de la trouver.
si quelqu'un pouvait m'aider ce serais super
j'ai trouver un package Boost, mais y'a pas la lib Graph :s
Merci.
je chercher a installer la lib graph Boost sous Cygwin, mais pas moyen de la trouver.
si quelqu'un pouvait m'aider ce serais super
j'ai trouver un package Boost, mais y'a pas la lib Graph :s
Merci.
mamiemando
Messages postés
33129
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
27 mai 2024
7 755
16 févr. 2009 à 15:31
16 févr. 2009 à 15:31
Tu peux la télécharger directement sur le site de boost. L'essentiel de la BGL étant des headers (hormis deux trois truc genre le binding avec graphviz) tu ne devrais pas avoir trop de soucis.
https://sourceforge.net/projects/boost/
Bonne chance
https://sourceforge.net/projects/boost/
Bonne chance