Algorithmique sur les graphes..
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
quelques idées en vrac (non, je ne ferai pas ton DM :-p surtout que c'est en C :( )
Citation:
'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.
ouep :-)
Citation:
Lorsqu'une rue devient critique, le graphe perd sa connexité.
Lorsqu'une rue est critique et est barrée !
Citation:
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é)
Je ne suis pas sûr à 100% que la terminologie soit bien arrêtée dans ce domaine, mais je pense que c'est bon.
Citation:
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?
D'un point de vue algorithmique, les deux sont globalement équivalente. La représentation sous forme de liste est à privilégié pour les graphes creux (nombre d'arrete globalement linéaire par rapport au nombre de sommet), la représentation matricielle pour les graphes plein (nombre d'arrete globalement quadratique en le nombre de sommet). Dans le cas d'une ville, ce serait clairement une représentation sous forme de liste. Mais est ce que les "villes" du problème ressemblent à des vraies villes, je n'en ai aucune idée :-)
Pour une piste : s'il n'y a pas de rue critiques, entre chaque carrefour il existe au moins deux chemins distincts, et donc un cycle comprenant ces deux carrefours.
Have fun, et n'hésite pas à reposter !
