Scribd Logo
Importer

Bienvenue sur Scribd !

  • 89 vues

    TD2 Graphe

    Transféré par

    Wiem Melki
    Le document présente cinq exercices sur la théorie des graphes, incluant la recherche de chaînes Eulériennes, l'application de l'algorithme de Kruskal, et la recherche de plus courts chemins.

    Droits d'auteur :

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

    TD2 Graphe

    Transféré par

    Wiem Melki
    89 vues2 pages
    Le document présente cinq exercices sur la théorie des graphes, incluant la recherche de chaînes Eulériennes, l'application de l'algorithme de Kruskal, et la recherche de plus courts chemins.

    Titre original

    TD2graphe (1)

    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 présente cinq exercices sur la théorie des graphes, incluant la recherche de chaînes Eulériennes, l'application de l'algorithme de Kruskal, et la recherche de plus courts chemins.

    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
    89 vues2 pages

    TD2 Graphe

    Transféré par

    Wiem Melki
    Le document présente cinq exercices sur la théorie des graphes, incluant la recherche de chaînes Eulériennes, l'application de l'algorithme de Kruskal, et la recherche de plus courts chemins.

    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

    Série N° 2

    Théorie des graphes

    Exercice 1

    Déterminer une chaine Eulérienne dans chacun des graphes suivants :


    A

    B C

    E D

    Exercice 2

    Une chèvre, un chou et un loup se trouvent sur la rive d’un fleuve ; un passeur souhaite les
    transporter sur l’autre rive mais, sa barque étant trop petite, il ne peut transporter qu’un seul
    d’entre eux à la fois. Comment doit-il procéder afin de ne jamais laisser ensemble et sans
    surveillance le loup et la chèvre, ainsi que la chèvre et le chou ?

    Exercice 3

    Appliquez l’algorithme de Kruskal sur le graphe suivant pour trouver un arbre couvrant de
    poids minimal ainsi que son poids.
    Exercice 4

    Remplir le tableau suivant qui, pour le graphe pondéré ci-dessous, donne la valeur du plus
    court chemin d’un sommet à un autre.

    A B C D E F G
    A
    B
    C
    D
    E
    F
    G

    Exercice 5

    Chercher le plus court chemin de A vers K dans le graphe suivant

    Vous aimerez peut-être aussi