Scribd Logo
Importer

Bienvenue sur Scribd !

  • 5 vues

    Exam Janv17 Graphes

    Transféré par

    yasminestudies123

    Droits d'auteur :

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

    Exam Janv17 Graphes

    Transféré par

    yasminestudies123
    5 vues2 pages

    Titre original

    exam-janv17-graphes

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

    Exam Janv17 Graphes

    Transféré par

    yasminestudies123

    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

    Examen é rit de théorie des graphes

    Janvier 2017

    Consignes : Il est attendu que les réponses fournies soient lairement justiées. La
    larté, la réda tion et la justi ation des réponses fournies interviennent dans la
    otation.
    Bon travail !
    Théorie (uniquement pour les étudiants ayant passé le projet)
    (1) Enon er et démontrer une ondition né essaire et susante pour qu'un
    graphe orienté soit eulérien.
    (2) Enon er le théorème de Dira donnant une ondition susante pour qu'un
    graphe soit hamiltonien.
    (3) Soit le graphe G représenté i-dessous.

    √ q √  q √ 
    Sa hant que 2 ≃ 1, 41 ; 12 5 + 21 ≃ 2, 19 et 12 5 − 21 ≃ 0, 46
    sont valeurs propres de G, quelles sont les autres valeurs propres de G ?
    La matri e d'adja en e de G est-elle primitive ? Justier vos réponses.
    (4) Soit l'arbre représenté i-dessous. Fournir les par ours préxe, inxe et
    suxe des sommets.
    1

    2 3

    4 5 6

    7 8 9 10

    Exer i es (pour tous)


    (1) (5 points) Soit G un graphe simple ayant n sommets et n − 1 arêtes qui
    n'est pas un arbre. (On suppose qu'un sommet isolé est un arbre "trivial".)
    (a) Prouver que G n'est pas onnexe.
    (b) Prouver que G possède une omposante onnexe qui est un arbre.
    ( ) Prouver que G possède une omposante onnexe qui n'est pas un arbre.
    (d) Prouver que si G possède exa tement deux omposantes onnexes, alors
    elle qui n'est pas un arbre possède exa tement un y le.
    2

    (2) (5 points) Soit le graphe G à 12 sommets représenté i-dessous.

    (a) Ce graphe est-il hamiltonien ? Quelle est sa fermeture ?


    (b) Ce graphe est-il eulérien ?
    ( ) Montrer que G est un graphe 4- olorable qui n'est pas 3- olorable.
    (d) Ajouter au plus 3 arêtes au graphe pour qu'il ne soit plus planaire.
    (e) Représenter le dual de ette représentation planaire de G. Quel est
    le nombre minimum de ouleurs à utiliser pour olorer les fa es ette
    représentation planaire de G, des fa es adja entes re evant des ouleurs
    distin tes ?
    (3) (5 points) On onsidère la matri e
     
    0 1 1 0
    0 0 1 0
    M =
    0

    0 0 1
    1 0 0 0
    (a) Représenter le graphe orienté D ayant M omme matri e d'adja en e.
    (b) Prouver que la matri e M est primitive. Est-il possible de supprimer
    un unique ar au graphe D pour rendre la matri e orrespondante irré-
    du tible mais non primitive ?
    ( ) Soit α la valeur propre de Perron de M . Quels renseignements peut-on
    tirer de M n quand n tend vers l'inni ? (Un énon é théorique sut pour
    répondre à la question.)
    (d) En supposant les sommets de D numérotés de façon ompatible ave
    M , montrer que, pour tout n ≥ 4, le nombre de hemins fermés partant
    et arrivant en 1 de longueur n + 4 est égal à la somme des nombres
    de hemins fermés partant et arrivant en 1 de longueur n et eux de
    longueur n+1. En déduire le nombre de tels hemins fermés de longueur
    16 passant par 1.

    (4) (5 points) On onsidère un graphe planaire onnexe G ayant 32 fa es tri-


    angulaires et 6 fa es arrées. De haque sommet de G partent quatre fa es
    triangulaires et une fa e arrée. Déterminer le nombre de sommets et le
    nombre d'arêtes de G.

    Vous aimerez peut-être aussi