Scribd Logo
Importer

Bienvenue sur Scribd !

  • 14 vues

    Graphes Orientes

    Transféré par

    Youssef Hmem

    Droits d'auteur :

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

    Graphes Orientes

    Transféré par

    Youssef Hmem
    14 vues6 pages

    Titre original

    graphes-orientes

    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
    14 vues6 pages

    Graphes Orientes

    Transféré par

    Youssef Hmem

    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 6

    Graphes Orientés

    1. Définitions p2
    2. Exercice 1 p3
    3. Exercice 2 p3

    Copyright  meilleurenmaths.com. Tous droits réservés


    Graphes Orientés

    1. Définitions
    . Un graphe orienté est un graphe dont les arêtes sont orientées (c'est à dire : on ne peut parcourir les arêtes
    que dans un sens).
    Exemple :

    . Une boucle est une arête orientée dont l'origine et l'extrémité sont confondues.
    Exemple

    . Matrice associée à une graphe orienté


    On numérote les sommets suivant l'ordre alphabétique .
    Pour le premier exemple :

    ( )
    0 1 1 1
    M= 0 0 1 1
    0 0 0 0
    0 0 1 0
    a 12=1 1ère ligne et 2 ème colonne
    car il y a une arête orientée de A vers B
    a 21=0 2 ème ligne et 1ère colonne
    car il n'existe pas d'arête orientée de B vers A.
    La matrice associée à un graphe orienté n'est pas nécessairement symétrique.
    Pour le deuxième exemple

    ( )
    1 1 0
    M= 0 0 1
    0 0 1

    Copyright  meilleurenmaths.com. Tous droits réservés Page 2


    Graphes Orientés
    2. Exercice 1
    Un club de tennis doit sélectionner deux joueurs parmi quatre pour représenter le club à un tournoi régional.
    Les quatre joueurs sont notés : A ; B ; C et D.
    Pour réaliser la sélection le club organise des matchs : chaque joueur rencontre les trois autres.
    Tout match gagné donne un point, tout match perdu enlève un point.
    Les joueurs sélectionnés sont les joueurs ayant obtenus le plus grand nombre de points.
    On donne le résultat sous la forme d'un graphe orienté.
    Remarque :
    Une flèche orientée de A vers B indique que le joueur A a battu le joueur B.

    Conséquence
    Le joueur A a gagné 3 matchs donc 3 points.
    Le joueur B a gagné 2 matchs et perdu 1 match donc 1 point.
    Le joueur C a perdu 3 matchs donc -3 points.
    Le joueur D a gagné 1 match et perdu 2 matchs donc -1 point.
    Les joueurs A et B sont donc sélectionnés.

    3. Exercice 2 ( sujet bac Liban mai 2006)


    1. Dans un parc, il y a cinq bancs reliés entre eux par des allées.
    On modélise les bancs par les sommets A, B, C, D,E et les allées par les arêtes du graphe G ci-dessous :

    Graphe G

    Copyright  meilleurenmaths.com. Tous droits réservés Page 3


    Graphes Orientés
    a. On désire peindre les bancs de façon que deux bancs reliés par une allée soient toujours de couleurs diffé-
    rentes.
    Donner un encadrement du nombre minimal de couleurs nécessaires et justifier.
    Déterminer ce nombre.
    b. Est-il possible de parcourir toutes les allées de ce parc sans passer deux fois par la même allée ?
    2. Une exposition est organisée dans le parc. La fréquentation devenant trop importante, on décide d'instaurer
    un plan de circulation : certaines allées deviennent à sens unique, d'autre reste à double sens. Par exemple la
    circulation dans l'allée située entre les bancs B et C pourra se faire de B vers C et de C vers B, alors que la
    circulation dans l'allée située entre les bancs A et B ne porra se faire que de A vers B. le graphe G' ci-dessous
    modélise cette nouvelle situation :

    Graphe G'
    a. Donner la matrice M associée au graphe G'. (On ordonnera les sommets par ordre alphabétique).

    ( )
    1 6 9 6 10
    4 5 7 11 5
    5
    b. On donne M = 4 6 6 11 5
    1 5 10 6 10
    6 5 5 14 2
    Combien ya-t-il de chemins de longuer 5 permettant de se rendre du sommet D au sommet B ?
    Les donner tous.
    c. Montrer qu'il existe un seul cycle de longueur 5 passant par A.
    Quel est ce cycle ?
    En est-il de même pour le sommet B ?
    CORRECTION
    1. Les sommets B et D sont de degré 3 et les sommets A, C et E sont de degré 2.
    Δ=3
    Le nombre chromatique est inférieur ou égal à Δ+1=4 .
    Si on considère le sous graphe B ; C ; D, ce sous graphe est complet, donc le nombre chromatique est supé-
    rieur ou égal à 3.
    Conclusion

    Copyright  meilleurenmaths.com. Tous droits réservés Page 4


    Graphes Orientés
    Le nombre chromatique est compris entre 3 et 4.
    Pour le déterminer, on colorie le graphe G en utilisant l'algorithme de coloration.
    Liste ordonnée des sommets : B ; D ;A ; C; E
    Liste ordonnée des couleurs : Rouge ; Vert ; Jaune . . .

    On a déterminé une coloration du graphe contenant 3 couleurs, donc le nombre chromatique est égal à 3.
    b. Il y a deux et seulement 2 sommets de degré impair, le théorème d'Euler permet d'affirmer qu'il existe au
    moins une chaîne eulérienne c'est à dire on peut parcourir toutes les allées de ce parc sans passer deux fois
    par la même allée.
    Exemple de chaîne eulérienne : BDEABCD.

    ( )
    0 1 0 0 1
    0 0 1 1 0
    2.a. M= 0 1 0 1 0
    0 0 1 0 1
    1 0 0 1 0

    b. Le cefficient a 42=5 dans M 5 donc il y a 5 chemins de longueur 5 reliant D en B.


    DEDEAB DEAEAB DCDEAB DCBDCB DEABCB
    c. Le coefficient a 11=1 dans M 5 donc il y a une seule chaîne fermée de longueur 5 d'origine et d'extrémité A.
    On détermine cette chaîne ABCDEA et cette chaîne est un cycle de longueur 5.
    Remarque
    Tout cycle de longueur 5 passant par A est une chaîne fermée de longueur 5 d'origine et d'extrémité A.
    Conclusion
    Il existe un seul cycle de longueue 5 passant par A.

    Le coefficient a 22=5 dans M 5 donc il existe 5 chaînes fermées de longueur 5 d'origine et d'extrémité B.
    On détermine ces 5 chaînes.
    BCDEAB cette chaîne est un cycle.
    BCBDCB cette chaîne n'est pas un cycle, elle contient deux fois l'arête CB.
    BDEDCB cette chaîne est un cycle .

    Copyright  meilleurenmaths.com. Tous droits réservés Page 5


    Graphes Orientés
    BDCDCB cette chaîne n'est pas un cycle, elle contient deux fois l'arête DC.
    BDCBCB cette chaîne n'est pas un cycle, elle contient deux fois l'arêteCB.
    Conclusion
    Il existe deux cycles de longueur 5 passant par B.

    Copyright  meilleurenmaths.com. Tous droits réservés Page 6

    Vous aimerez peut-être aussi