mek-city33 Posted July 22, 2007 Share Posted July 22, 2007 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. PS: Je suis débutant en programmation et je trouve que le sujet est intéressant et ce pour cela que je demande de l'aide Link to comment Share on other sites More sharing options...
theocrite Posted July 23, 2007 Share Posted July 23, 2007 Et quelle est la question exactement ? Link to comment Share on other sites More sharing options...
beuhbeuh Posted July 30, 2007 Share Posted July 30, 2007 La question est : "pouvez-vous faire à ma place mon exo sur les graphes ?" Link to comment Share on other sites More sharing options...
LukeSkyPator Posted July 30, 2007 Share Posted July 30, 2007 La réponse est 42 LSP, le manchot useless Link to comment Share on other sites More sharing options...
Recommended Posts
Archived
This topic is now archived and is closed to further replies.