Algorithmique sur les graphes
Répondre à la discussion
Affichage des résultats 1 à 17 sur 17

Algorithmique sur les graphes



  1. #1
    invite0eb43bcc

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


    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

    -----

  2. #2
    invite765732342432
    Invité

    Re : Algorithmique sur les graphes

    Citation Envoyé par mek-city33 Voir le message
    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

  3. #3
    invite7a8ce750

    Re : Algorithmique sur les graphes

    Citation Envoyé par Faith Voir le message
    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.

  4. #4
    invite0eb43bcc

    Re : Algorithmique sur les graphes

    Citation Envoyé par Faith Voir le message
    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

  5. A voir en vidéo sur Futura
  6. #5
    invite0eb43bcc

    Re : Algorithmique sur les graphes

    Citation Envoyé par Faith Voir le message
    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.

  7. #6
    invite79d10163

    Re : Algorithmique sur les graphes

    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,

  8. #7
    invite79d10163

    Re : Algorithmique sur les graphes

    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.

  9. #8
    invite0eb43bcc

    Re : Algorithmique sur les graphes

    Citation Envoyé par skydancer Voir le message
    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

  10. #9
    invite2a419956

    Lightbulb Re : Algorithmique sur les graphes

    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

  11. #10
    invite7a8ce750

    Angry Re : Algorithmique sur les graphes

    Citation Envoyé par zouiz Voir le message
    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 !!!

  12. #11
    invite7a8ce750

    Re : Algorithmique sur les graphes

    Citation Envoyé par mek-city33 Voir le message
    [...]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.

  13. #12
    invite79d10163

    Re : Algorithmique sur les graphes

    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.

  14. #13
    invite0eb43bcc

    Re : Algorithmique sur les graphes

    Citation Envoyé par Gre Voir le message
    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.

  15. #14
    invite7a8ce750

    Re : Algorithmique sur les graphes

    Citation Envoyé par mek-city33 Voir le message
    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.

  16. #15
    invite765732342432
    Invité

    Re : Algorithmique sur les graphes

    Citation Envoyé par mek-city33 Voir le message
    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 ?

  17. #16
    invite0eb43bcc

    Post Re : Algorithmique sur les graphes

    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

  18. #17
    invite0eb43bcc

    Re : Algorithmique sur les graphes

    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

Discussions similaires

  1. Probleme sur les graphes
    Par invite0eb43bcc dans le forum Logiciel - Software - Open Source
    Réponses: 0
    Dernier message: 24/08/2007, 12h06
  2. Problème sur les graphes.
    Par invite722c8242 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 25/02/2007, 11h36
  3. Un exercice sur les graphes probabilistes terminé..
    Par invitebf58d26c dans le forum Mathématiques du collège et du lycée
    Réponses: 3
    Dernier message: 27/04/2006, 15h54
  4. Problème sur les graphes
    Par invite3b09ac13 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 04/02/2006, 14h10
  5. Question sur les Graphes
    Par invite6792ca02 dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 30/06/2005, 14h29
Dans la rubrique Tech de Futura, découvrez nos comparatifs produits sur l'informatique et les technologies : imprimantes laser couleur, casques audio, chaises gamer...