Scribd Logo
Importer

Bienvenue sur Scribd !

  • 56 vues

    Examen

    Transféré par

    ayetderki
    Le document contient quatre exercices portant sur des algorithmes de graphes comme le parcours en largeur, parcours en profondeur, arbre couvrant minimal, plus court chemin. Les exercices demandent d'appliquer ces algorithmes sur des graphes donnés et de répondre à des questions annexes.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    Examen

    Transféré par

    ayetderki
    56 vues2 pages
    Le document contient quatre exercices portant sur des algorithmes de graphes comme le parcours en largeur, parcours en profondeur, arbre couvrant minimal, plus court chemin. Les exercices demandent d'appliquer ces algorithmes sur des graphes donnés et de répondre à des questions annexes.

    Titre original

    examen RO

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Le document contient quatre exercices portant sur des algorithmes de graphes comme le parcours en largeur, parcours en profondeur, arbre couvrant minimal, plus court chemin. Les exercices demandent d'appliquer ces algorithmes sur des graphes donnés et de répondre à des questions annexes.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    56 vues2 pages

    Examen

    Transféré par

    ayetderki
    Le document contient quatre exercices portant sur des algorithmes de graphes comme le parcours en largeur, parcours en profondeur, arbre couvrant minimal, plus court chemin. Les exercices demandent d'appliquer ces algorithmes sur des graphes donnés et de répondre à des questions annexes.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    sur 2

    Ecole Supérieure Informatique ‫المدرسة العليا للعلم اللي‬

    Sidi Bel Abbes ‫سيدي بلعباس‬

    Module :Recherche Opérationnelle


    Durée : 02 h 00

    EXAMEN 01
    21/11/2018

    Exercice 01 : (4,5 pts)


    NB : Pour cet exercice , respecter l'ordre croissant des sommets lorsqu'il s'agit de faire un choix.

    Étant donné le graphe G représenté ci contre :


    1 – Appliquer l'algorithme de parcours en largeur BFS (1 pt)
    2– Appliquer l'algorithme de parcours en profondeur DFS (1pt)
    3 – Quelle est la densité de ce graphe ? (0,5 pt) Et quelle est la
    somme de ses degrés ? (0,5 pt)
    4 –Dessiner S le sous graphe de G engendré par les sommet :
    5,7,8,6,9, 11,10 (0,5 pts) et P un graphe partiel de G assurant un
    degré de 2 pour chaque sommet. (0,5 pt)
    5- Est ce que ce graphe est semi-eulérien ? justifier votre
    réponse (0,5 pt).

    Exercice 02 : (05 pts)


    Étant donné le graphe G non orienté pondéré suivant :
    1 - En prenant comme point de départ le sommet 0,
    Appliquer l'algorithme de Prim pour construire l’arbre
    couvrant minimal(2pt). Donner le poids de cet arbre (0,5pt).
    2- Donner le code de Prüfer de l'ACPM retrouvé à la
    question précédente (1 pt).
    3– Si les arêtes de ce graphe expriment une relation
    d'incompatibilité, proposer une coloration du graphe en
    utilisant l'algorithme Welsh et Powell (1,5 pt).

    Exercice 03 : (3,5 pts)


    1 - Dessinez le graphe G qui admet pour matrice d’adjacence
    la matrice M : (0,25 pt)

    2- a -Calculez (produit non booléen) M² , M3 , puis M+M² . (1,5 pt)


    b - Que signifie la présence de 0 à la position (i,j) dans la matrice M3 (0,25 pt)
    c - Que signifie la présence de 0 à la position (i,j) dans la matrice M+M² (0,25 pt)
    3 - Combien y a-t-il de chemins de longueur 2 menant 1 à 2 ? 2 à 4 ? (0,5 pt)
    4 - Combien y a-t-il de chemins de longueur ≤ 2 menant 1 à 2 ? 2 à 4 ? (0,5 pt)
    5 - Comment détecter la présence d'un cycle à travers la fermeture transitive ? (0,25 pt)

    NB : la clarté et la lisibilité des réponses sont évaluées sur 01 pt.


    Ecole Supérieure Informatique ‫المدرسة العليا للعلم اللي‬
    Sidi Bel Abbes ‫سيدي بلعباس‬

    Module :Recherche Opérationnelle


    Durée : 02 h 00

    Exercice 04 : (6 pts)
    Etant donné le graphe pondéré et orienté suivant :

    1. Utiliser l’algorithme Dijikstra pour calculer les plus


    courts chemins issus de a. (2,5 pts). Enumérer tous ces
    chemins ainsi que les distances correspondantes. (0,5 pt)
    2. La longueur de l’arc ge est en fait -8. Utiliser cette fois
    l’algorithme de Bellman-Ford pour trouver les plus
    courts chemins issus de a. On traitera les arcs selon
    l’ordre alphabétique. (2,5 pts)
    3. Une seconde modification a lieu, la longueur de l’arc
    fh est maintenant de 1 (la longueur de ge est toujours -8). Peut on relancer l’algorithme de Bellman-
    Ford. Justifier votre réponse. (0,5 pts)

    NB : la clarté et la lisibilité des réponses sont évaluées sur 01 pt.

    Vous aimerez peut-être aussi