Algorithmiques sur les graphes

[mek-city33]

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

[theocrite]

Et quelle est la question exactement ?

[beuhbeuh]

La question est : "pouvez-vous faire à ma place mon exo sur les graphes ?"

[LukeSkyPator]

La réponse est 42

LSP, le manchot useless