Scribd Logo
Importer

Bienvenue sur Scribd !

  • 635 vues

    Serie 2 - Correction

    Transféré par

    Salma Chaieb
    Le document décrit plusieurs exercices sur la théorie des graphes, notamment la coloration de graphes et les couplages dans les graphes bipartis.

    Droits d'auteur :

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

    Serie 2 - Correction

    Transféré par

    Salma Chaieb
    635 vues3 pages
    Le document décrit plusieurs exercices sur la théorie des graphes, notamment la coloration de graphes et les couplages dans les graphes bipartis.

    Titre original

    serie 2 - correction

    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 décrit plusieurs exercices sur la théorie des graphes, notamment la coloration de graphes et les couplages dans les graphes bipartis.

    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
    635 vues3 pages

    Serie 2 - Correction

    Transféré par

    Salma Chaieb
    Le document décrit plusieurs exercices sur la théorie des graphes, notamment la coloration de graphes et les couplages dans les graphes bipartis.

    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 3

    FACULTE DES

    SCIENCES DE Département d’informatique


    MONASTIR Année Universitaire : 2019-2020

    Travaux dirigés n° 2
    (Correction)
    Matière : Théorie des graphes
    Filière : LFI2

    Exercice n° 1
    Un lycée doit organiser les horaires des examens. On suppose qu’il y a 7 épreuves à planifier,
    correspondant aux cours numérotés de 1 à 7 et que les paires de cours suivantes ont des
    étudiants communs : 1 et 2, 1 et 3, 1 et 4, 1 et 7, 2 et 3, 2 et 4, 2 et 5, 2 et 7, 3 et 4, 3 et 6, 3 et
    7, 4 et 5, 4 et 6, 5 et 6, 5 et 7 et enfin 6 et 7.
    Comment organiser ces épreuves de façon qu’aucun étudiant n’ait à passer deux épreuves en
    même temps et cela sur une durée minimale ?
    1ère Solution:
    Construisons le graphe G dont les sommets sont les épreuves numérotées de 1 à 7, une arête
    reliant deux sommets lorsque les deux cours correspondant possèdent des étudiants communs.

    Planifier les examens en un temps minimal consiste à déterminer une k-coloration de G avec k
    = γ(G) : G possède une clique d’ordre 4 (de sommets 1, 2, 3, 4), donc γ(G) ≥ 4. Déterminons
    une partition des sommets de G en sous-ensembles stables : S1 = {1,5}, S2 = {2,6},S3 =
    {3},S4 = {4,7}, d’où γ(G) ≤ 4. On en déduit que γ(G) = 4.
    Les examens peuvent être répartis en 4 périodes, de la manière suivante :
    1ère période (rouge) : épreuves des cours 1 et 5.
    2ème période (vert) : épreuves des cours 2 et 6.
    3ème période (jaune) : épreuve du cours 3.
    4ème période (bleu) : épreuves des cours 4 et 7.
    2ème Solution:
    En appliquant l’algorithme de coloration on obtient :
    deg sommet couleur
    5 2 C1
    5 3 C2
    5 4 C3
    5 7 C3
    4 1 C4
    4 5 C2
    4 6 C1
    1
    Les examens peuvent être répartis en 4 périodes, de la manière suivante :
    1ère période (rouge) : épreuves des cours 2 et 6.
    2ème période (vert) : épreuves des cours 3 et 5.
    3ème période (bleu) : épreuves des cours 4 et 7.
    4ème période (jaune) : épreuve du cours 1.
    Exercice n° 2
    Une entremetteuse essaie de former le plus de couples possible avec 6 filles et 6 garçons en
    fonction de critères esthétiques et de compatibilité d’humeur. Elle a dressé le tableau
    d’incompatibilités ci-après, où une croix indique que deux personnes sont incompatibles.
    Combien de couples pourra-t-elle former au maximum ?

    Solution :

    On cherche un couplage maximal dans le graphe biparti ci-dessous (qui représente les couples
    possibles) :

    Il existe un couplage parfait. Donc, on peut donc former six couples.

    Exercice n° 3
    Décrivez le graphe G ci-dessous par une matrice d’adjacences et des listes d’adjacences.

    2
    Matrice d’adjacences Liste d’adjacences

    Exercice n° 4
    Modéliser les différents arbres avec 1, 2, 3, 4, 5, 6, et 7 sommets ?

    Exercice n° 5
    Dessiner l’arbre correspondant à la suite S = {2,3,3,3} ou I = {1,2,3,4,5,6}

    Vous aimerez peut-être aussi