Scribd Logo
Importer

Bienvenue sur Scribd !

  • 186 vues

    Td1graphe PDF

    Transféré par

    mona

    Droits d'auteur :

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

    Td1graphe PDF

    Transféré par

    mona
    186 vues2 pages

    Titre original

    td1Graphe.pdf

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

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

    Td1graphe PDF

    Transféré par

    mona

    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

    Universitéde Monastir A.

    U : 2020-2021
    Institut Supérieur d'Informatique de Mahdia
    Série 1 : Graphes simples

    Exercice 1 :
    Trois professeurs P1 , P2 , P3 devront donner lundi prochain un certain
    nombre d'heures de cours à trois classes C1 , C2 , C3 :
     P1 doit donner 2 heures de cours à C1 et 1 heure à C2;
     P2 doit donner 1 heure de cours à C1 , 1 heure à C2 et 1 heure à C3;
     P3 doit donner 1 heure de cours à C1 , 1 heure à C2 et 2 heures à C3.
    1. Comment représenter cette situation par un graphe?
    2. Quel type de graphe obtenez-vous?
    3. Combien faudra-t-il de plages horaires au minimum?
    4. Aidez-vous du graphe pour proposer un horaire du lundi pour ces
    professeurs.
    Exercice 2 :

    Un tournoi d'échecs oppose 6 personnes. Chaque joueur doit aronter


    tous les autres.
    1. Construisez un graphe représentant toutes les parties possibles.
    2. Quel type de graphe obtenez-vous?
    3. Si chaque joueur ne joue qu'un match par jour, combien de jours
    faudra-t-il pour terminer le tournoi?
    4. Aidez-vous du graphe pour proposer un calendrier des matches.
    Exercice 3 :
    On considère le graphe simple G déni sur V = {1, . . . , 6} par :
    E = {{x, y} ∈ V ; x divise y}
    2

    1. Constuire le graphe G.
    2. Donner le degré de chaque sommet de G.
    Exercice 4 :
    Montrez qu'un graphe simple a un nombre pair de sommets de degré impair.
    Exercice 5 :
    Est-il possible de relier 15 ordinateurs de sorte que chaque appareil soit
    relié avec exactement trois autres?
    Exercice 6 :
    On s'intéresse aux graphes réguliers de degré 3.
    1. Quel est le nombre minimum de sommets que doit posséder un graphe
    régulier de degré 3?
    2. Construire, s'il est possible, de tels graphes ayant 4, 5, 6, puis 7 som-
    mets.
    3. Que déduisez-vous? Prouvez-le.
    Exercice 7 :

    Soit G un graphe simple d'ordre 12 à 14 arêtes dont les sommets sont de


    degré 2 ou 3. Donner le nombre de sommets de degré 2 ainsi que le nombre
    de sommets de degré 3.
    Exercice 8 :

    Soit G un graphe simple d'ordre n ≥ 2.


    1. Montrer qu'il existe au moins deux sommets distincts de G qui ont le
    même degré.
    2. En déduire que dans une assemblée de n personnes, il y a au moins
    deux personnes qui ont le même nombre d'amis dans cette assemblée.

    Vous aimerez peut-être aussi