Scribd Logo
Importer

Bienvenue sur Scribd !

  • 41 vues

    1er TD Graphe

    Transféré par

    Rihem Dridi

    Droits d'auteur :

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

    1er TD Graphe

    Transféré par

    Rihem Dridi
    41 vues3 pages

    Titre original

    1er-TD-Graphe (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é ?

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

    1er TD Graphe

    Transféré par

    Rihem Dridi

    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

    Concepts fondamentaux de la théorie des graphes

    TD N° 1

    Exercice n°1 :
    Déterminer le degré de chacun des sommets du graphe ci-dessous :

    Exercice n° 2 :
    Un tournoi d’échecs oppose 6 personnes. Chaque joueur doit affronter tous les autres.
    1. Construisez un graphe représentant toutes les parties possibles.
    2. Quel type de graphe obtenez-vous ? Si chaque joueur ne joue qu’un match par jour,
    combien de jours faudra-t-il pour terminer le tournoi ?
    3. Aidez-vous du graphe pour proposer un calendrier des matches

    Exercice n° 3 :
    Trois pays envoient chacun à une conférence deux espions ; chaque espion doit espionner tous
    les espions des autres pays (mais pas son propre collègue).
    1. Représentez cette situation par un graphe d'ordre 6 dans lequel chaque arête reliant i
    et j signifie que i espionne j que et j espionne i.
    2. Ce graphe est-il complet ? Est-il connexe ?
    3. Quel est le degré de chaque sommet ? Déduisez-en le nombre d'arêtes.
    Exercice n° 4 :
    Peut-on construire un graphe simple (aucune arête n’est une boucle et il y a au plus une arête
    entre deux sommets) ayant :
    a. 4 sommets et 7 arêtes.
    b. 5 sommets et 11 arêtes.
    c. 10 sommets et 46 arêtes.
    Exercice n° 5 :
    Le graphe ci-dessous indique, les parcours possibles entre sept classes d’un institut
    universitaire. Un agent de l’administration effectue régulièrement des rondes de surveillance.
    Ses temps de parcours en minutes entre deux salles sont les suivants :

    1 Fedia Arfaoui
    Concepts fondamentaux de la théorie des graphes

    AB : 16 minutes ; AG = 12 minutes ;
    BC = 8 minutes ; BE : 12 minutes ;
    BG : 8 minutes ; CD : 7 minutes ;
    CE = 4 minutes ; CG : 10 minutes ;
    DE : 2 minutes ; EF : 8 minutes ;
    EG : 15 minutes ; FG : 8 minutes.
    Sur chaque arête, les temps de parcours sont indépendants du sens du parcours.
    1. Montrer qu’il est possible que l’agent de sécurité passe une fois et une seule par tous
    les chemins de cette usine. Donner un exemple de trajet.
    2. L’agent de sécurité peut-il revenir à son point de départ après avoir parcouru une fois
    et une seule tous les chemins ? Justifier la réponse.
    Exercice n° 6 :
    Papa noël doit déblayer les 6 routes qui relient 5 villages A, B, C, D et E, Peut-on trouver des
    itinéraires qui permettent de parcourir une et une seule fois chaque route ?
    a. En partant de E et en terminant par E.
    b. En partant de C et en terminant à D.
    c. En partant de A et en terminant à A.

    Exercice n° 7 :
    1. Donner la matrice d’incidence sommets-arêtes et la matrice d’adjacence sommets-
    sommets du graphe suivant :

    2. Donner la matrice d’incidence sommets-arcs et la matrice d’adjacence sommets-


    sommets du graphe suivant :
    2 Fedia Arfaoui
    Concepts fondamentaux de la théorie des graphes

    3. Représenter graphiquement les graphes associés aux matrices d’incidence sommets-


    arcs suivantes :

    4. Représenter graphiquement le graphe associé à la matrice d’adjacence sommets-


    sommets suivante :

    3 Fedia Arfaoui

    Vous aimerez peut-être aussi