Algorithmique sur les graphes
Résolu
Bonjour,
J'ai besoin d'aide à propos du problème sur les graphes suivant (je ne sais pas d'où commencer):
On considère une ville formé d'un certain nombre de carrefours relié entre eux par des
rues (aucune supposition n'est faite sur la possibilité ou non de représenter sur un plan
de manière à ce que les rues ne se croisent pas; il est possible que certaines "rues"
empruntent des souterrains ou des ponts suspendus). On suppose qu'il est normalement
possible de se déplacer de n'importe quel carrefour a n'importe quel autre en empruntant
une succession de rues.
On considère q'une rue est critique si, lorsqu'elle est soudainement barrée (alors
qu'aucune autre rue n'est barrée), il devint impossible de se déplacer de certains
carrefours à certains autres.
Un édile fou décide d'instaurer un sens unique sur chacune des rues.A un de ses opposants
qui s'inquiète des possibilités futures de circulation, il rétorque:"Notre ville ne
comporte actuellement aucune rue critique; par conséquent il est possible d'attribuer à
chacune des rues un sens unique de circulation, de telle manière qu'il reste possible de
passer de n'importe quel endroit à n'importe quel autre.Votre objection est donc rejeté".
Travail demandé:
On demande de modéliser la situation décrite ci-dessus en termes de graphes et de prouver
que l'affirmation du maire est effectivement correcte: pour toute ville imaginable, les
assertions "il n'existe aucune rue critique" et " il est possible de mettre toutes les
rues au sens unique sans rendre la circulation impossible" sont équivalentes. Décrire un algorithme, qui étant donné une ville, exhibe soit une rue critique, soit une solution au problème des sens uniques ; et étudier sa complexité.
Réaliser un programme C offrant au moins les fonctionnalités suivantes :
• Lire, dans un fichier ou clavier, une description d’une « ville ».
• Ecrire dans un fichier une description d’une « ville ».
• Etant donné une « ville », décide si le problème des sens uniques admet une solution et, dans le cas positif, exhibe une telle solution.
• Etant donné une « ville », décide si elle possède une rue critique et, c’est le cas, en exhibe une.
J'aimerais que vous me disiez si ceci est juste ou pas:
Se déplacer de n'importe quel carrefour à n'importe quel autre-->Graphe connexe.
Lorsqu'une rue devient critique, le graphe perd sa 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é)
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?
Merci
J'ai besoin d'aide à propos du problème sur les graphes suivant (je ne sais pas d'où commencer):
On considère une ville formé d'un certain nombre de carrefours relié entre eux par des
rues (aucune supposition n'est faite sur la possibilité ou non de représenter sur un plan
de manière à ce que les rues ne se croisent pas; il est possible que certaines "rues"
empruntent des souterrains ou des ponts suspendus). On suppose qu'il est normalement
possible de se déplacer de n'importe quel carrefour a n'importe quel autre en empruntant
une succession de rues.
On considère q'une rue est critique si, lorsqu'elle est soudainement barrée (alors
qu'aucune autre rue n'est barrée), il devint impossible de se déplacer de certains
carrefours à certains autres.
Un édile fou décide d'instaurer un sens unique sur chacune des rues.A un de ses opposants
qui s'inquiète des possibilités futures de circulation, il rétorque:"Notre ville ne
comporte actuellement aucune rue critique; par conséquent il est possible d'attribuer à
chacune des rues un sens unique de circulation, de telle manière qu'il reste possible de
passer de n'importe quel endroit à n'importe quel autre.Votre objection est donc rejeté".
Travail demandé:
On demande de modéliser la situation décrite ci-dessus en termes de graphes et de prouver
que l'affirmation du maire est effectivement correcte: pour toute ville imaginable, les
assertions "il n'existe aucune rue critique" et " il est possible de mettre toutes les
rues au sens unique sans rendre la circulation impossible" sont équivalentes. Décrire un algorithme, qui étant donné une ville, exhibe soit une rue critique, soit une solution au problème des sens uniques ; et étudier sa complexité.
Réaliser un programme C offrant au moins les fonctionnalités suivantes :
• Lire, dans un fichier ou clavier, une description d’une « ville ».
• Ecrire dans un fichier une description d’une « ville ».
• Etant donné une « ville », décide si le problème des sens uniques admet une solution et, dans le cas positif, exhibe une telle solution.
• Etant donné une « ville », décide si elle possède une rue critique et, c’est le cas, en exhibe une.
J'aimerais que vous me disiez si ceci est juste ou pas:
Se déplacer de n'importe quel carrefour à n'importe quel autre-->Graphe connexe.
Lorsqu'une rue devient critique, le graphe perd sa 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é)
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?
Merci
A voir également:
- Algorithmique sur les graphes
- Videosurveillance algorithmique - Accueil - Protection
- Comment faire un graphe sur excel - Guide
- Factorielle sur casio graph 35+e - Forum calculatrices
- Touche puissance sur calculatrice casio graph 35+e ✓ - Forum calculatrices
- Comment faire x sur une calculatrice casio graph 35+e ✓ - Forum calculatrices
11 réponses
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
De même, bon courage ;)
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
je cherche des exercices corrigés sur le cour "d'algorithmique des graphes" svp c'est trés urgent.
cordialement
cordialement
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
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
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.
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