Algorithmique sur les graphes

[invite0eb43bcc]

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
-----

[invite765732342432]

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

Débutant à quel point ? Sais-tu créer une liste chainée, ou un graphe ?
Sais-tu programmer en récursif (pas forcément nécessaire, mais peut être pratique) ?

Ensuite, il faut d'abord que tu puisses définir si une ville est "correcte" c'est à dire que tous les carrefours sont reliés les uns aux autres.
Pour savoir si une rue est critique, c'est alors très simple.
Pour résoudre le problème des rues à sens unique... c'est un peu plus difficile, mais l'algo naïf n'est pas très compliqué.

Les algos "naïfs" marchent bien, mais comme il t'est demandé d'étudier la complexité, tu vas sans doute tomber sur une très mauvaise complexité (mais sans réfléchir, je ne sais pas si on peut faire beaucoup mieux)

Pour plus de détails, dis-nous déjà ce que tu connais, ce que tu arrives à faire, et n'hésite pas à poser des questions

Bonne chance

[invite7a8ce750]

Débutant à quel point ? Sais-tu créer une liste chainée, ou un graphe ?
Sais-tu programmer en récursif (pas forcément nécessaire, mais peut être pratique) ?
[...]

C'est un cours d'algorithmique visiblement.
Donc avant même de penser liste chainée, il faut qu'il pense de manière abstraite à son algorithme.

mek-city33 qu'as tu produit comme (ébauche ?) d'algorithme.
Si ton algorithme est bon, tu verras après comment l'implémenter.
Mais si tu n'as pas fait cet étape, tu perds ton temps.

Pour faire ton algorithme, réflechis à la manière de résoudre ton problème sans penser programmation dans un premier temps. Faith t'a donné des indications.

[invite0eb43bcc]

Débutant à quel point ? Sais-tu créer une liste chainée, ou un graphe ?
Sais-tu programmer en récursif (pas forcément nécessaire, mais peut être pratique) ?

Ensuite, il faut d'abord que tu puisses définir si une ville est "correcte" c'est à dire que tous les carrefours sont reliés les uns aux autres.
Pour savoir si une rue est critique, c'est alors très simple.
Pour résoudre le problème des rues à sens unique... c'est un peu plus difficile, mais l'algo naïf n'est pas très compliqué.

Les algos "naïfs" marchent bien, mais comme il t'est demandé d'étudier la complexité, tu vas sans doute tomber sur une très mauvaise complexité (mais sans réfléchir, je ne sais pas si on peut faire beaucoup mieux)

Pour plus de détails, dis-nous déjà ce que tu connais, ce que tu arrives à faire, et n'hésite pas à poser des questions

Bonne chance

oui je sai faire des liste chainée et je sais programmer en récursive mais mon problème reste que j'arrive pas a écrire un algo qui résoud ce problème..en d'autres termes je ne sais pas d'où commencer mon algo.
Cordialement

[A voir en vidéo sur Futura]

[invite0eb43bcc]

Débutant à quel point ? Sais-tu créer une liste chainée, ou un graphe ?
Sais-tu programmer en récursif (pas forcément nécessaire, mais peut être pratique) ?

Ensuite, il faut d'abord que tu puisses définir si une ville est "correcte" c'est à dire que tous les carrefours sont reliés les uns aux autres.
Pour savoir si une rue est critique, c'est alors très simple.
Pour résoudre le problème des rues à sens unique... c'est un peu plus difficile, mais l'algo naïf n'est pas très compliqué.

Les algos "naïfs" marchent bien, mais comme il t'est demandé d'étudier la complexité, tu vas sans doute tomber sur une très mauvaise complexité (mais sans réfléchir, je ne sais pas si on peut faire beaucoup mieux)

Pour plus de détails, dis-nous déjà ce que tu connais, ce que tu arrives à faire, et n'hésite pas à poser des questions

Bonne chance

j'avais oublier de vous dire que j'arrive à programmer en C mais je ne suis pas assez fort quand même..le truc des liste chainées et doublement chainées je sais comment le faire...Enfin à vrai j'ai besoin que quelqu'un me propose une solution algorithmique pour ce problème et merci.

[invite79d10163]

Bonjour,

As-tu entendu parler d'isthme dans un graphe connexe ? C'est en quelques sortes l'équivalent d'une rue critique dans ta ville. Si tu as un cours la dessus tu pourras y trouver des idées pour chercher si un des arcs de ton graphe est un isthme. Sinon tu peux trouver un cours à l'adresse suivante:
www.univ-paris12.fr/lacl/cohen/poly_gr.ps

En gros tu auras besoin de faire un algo de "parcours en profondeur", voir page 23 à 30, tout y est expliqué. Bonne lecture,

[invite79d10163]

Bonjour,

Pour la preuve de "pas de rue critique => les rues peuvent être transformées en sens unique". Il y a une preuve vers la page 50.

[invite0eb43bcc]

Bonjour,

As-tu entendu parler d'isthme dans un graphe connexe ? C'est en quelques sortes l'équivalent d'une rue critique dans ta ville. Si tu as un cours la dessus tu pourras y trouver des idées pour chercher si un des arcs de ton graphe est un isthme. Sinon tu peux trouver un cours à l'adresse suivante:
www.univ-paris12.fr/lacl/cohen/poly_gr.ps

En gros tu auras besoin de faire un algo de "parcours en profondeur", voir page 23 à 30, tout y est expliqué. Bonne lecture,

Merci beacoup Skydancer....Je te contacterai si j'aurais besoin de quelque chose:
Cordialement

[invite2a419956]

Salut,

Dèja il faut implementer le graphe d'une manière qui te facilitera l'écriture des algo plus tard. Tu peux par exemple utiliser les listes d'adjacences ( en gros tu associe à chaque rond point la liste des rues qu'il dessert )

Si j'ai bien compris si une rue est critique alors le graphe n'est pas simplement connexe donc faudrai eventuellement commencer par écrire un algo qui renseigne sur la connexité du graphe.

Ensuite faudrai faire un algo qui prend chaque rue en double sens (arete), qui la "transforme" en sens unique (arc ( arete orienté)) qui teste si le graphe est toujours connexe ( si non hop rue suivante ) etc ...
En gros un algo qui teste si une rue est (ou pas) critique...

Voila quelques idées pour commencer bonne chance

[invite7a8ce750]

Dèja il faut implementer le graphe d'une manière qui te facilitera l'écriture des algo plus tard. [...]

Non ça c'est exactement un mauvais réflexe !

On n'implémente pas avant de réflechir à l'algorithme.
On réflechit à l'algorithme ce qui permet d'en déduire comment on implémente le graphe !!!

[invite7a8ce750]

[...]Enfin à vrai j'ai besoin que quelqu'un me propose une solution algorithmique pour ce problème et merci.

Si tu n'es même pas capable de commencer à penser comment faire, il faut que tu retournes voir ton prof. Ce n'est pas à nous de faire tes devoirs. En particulier parce que c'est à toi de travailler pour apprendre à résoudre le problème.

Si par contre tu as un début, alors apportes la solution ici et tu pourras trouver de l'aide. Pour l'instant il n'y a rien de ta part. Donc j'ose espérer que personne ne t'apportera une solution; pas moi en tout cas.

[invite79d10163]

Bonjour,

Il y a au moins deux façons très classique de travailer avec les graphes :
1) à l'aide de matrice d'adjacence, la matrice contient autant de ligne que deux noeud dans le graphe et on place des "1" dans la matrice quand le noeud "i" est connecté au noeud "j". Dans ce cas on travaille avec des tableaux. C'est simple à manipuler pour lorqu'on débute en programmation. Mais cette aproche est gourmande en mémoire, la matrice contient surtout des "0".

2) à l'aide de liste d'adjacence, On écrit en mémoire la liste des noeuds voisins pour chaque noeuds du graphe. Comme son nom l'indique on utilise des listes, un peu plus embettant à manipuler lorsqu'on en a pas l'habitude.

Tu peux par éxemple jeter un coup d'oeuil à la librairie Boost\graph pour un aperçu des structures de données les plus utlilisées.

[invite0eb43bcc]

Si tu n'es même pas capable de commencer à penser comment faire, il faut que tu retournes voir ton prof. Ce n'est pas à nous de faire tes devoirs. En particulier parce que c'est à toi de travailler pour apprendre à résoudre le problème.

Si par contre tu as un début, alors apportes la solution ici et tu pourras trouver de l'aide. Pour l'instant il n'y a rien de ta part. Donc j'ose espérer que personne ne t'apportera une solution; pas moi en tout cas.

ouai mais je tiens juste à signaler qu'il s'agit pas d'un devoir...Les cours ont terminés.

[invite7a8ce750]

ouai mais je tiens juste à signaler qu'il s'agit pas d'un devoir...Les cours ont terminés.

Pertinent comme remarque ^_^ ici les cours ne le sont pas....
Désolé alors pour ma remarque.

As tu progressé ?
Car il reste qu'une solution ne t'aidera pas à apprendre.

[invite765732342432]

ouai mais je tiens juste à signaler qu'il s'agit pas d'un devoir...Les cours ont terminés.

Salut Mek-city !
A priori, tu as dans toutes les réponses qui t'ont été faites suffisemment d'informations pour avancer sérieusement dans ton problème. En dire plus serait donner la (une) solution.

Et ce n'est pas un bon moyen de progresser en informatique.
Sur quoi peines-tu ? Peux-tu nous dire précisément ce qui te pose problème ?

[invite0eb43bcc]

Bonjour,
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

[invite0eb43bcc]

Pour l'implémentation des graphes non orientés j'ai pensé à utiliser des arcs tels que pour deux sommets u et v on définit un arc de u à v et un autre de v à u comme ça il est possible de se déplacer dans les deux sens.

PS: essayez de me répondre svp