Théorie des graphes


  • P

    Bonsoir,

    je commence une nouvelles matière, en plus en Espagnol (échange erasmus) ! Je n'y connais absolument rien en graphes, et on nous demande déjà de préparer des exercices !!

    Je fais donc appel à vous après en avoir bavé depuis quelques jours...J'ai deux énoncé, que je vais essayer de traduire le mieux possible !

    Exo1 :
    Soit G un graphe simple avec n sommets et q arrêtes tel que q> [Composition de 2 parmi (n-1)]. Prouver que G est connexe.

    Piste...: on arrive a q> ( (n-2)(n-1) ) /2. Il me semble qu'un graphe complet est connexe, et on dit qu'un graphe complet a q= (n * (n-1) ) /2. Il y a peut être une solution quelque part...

    Exo2 :
    Soit S={I1,I2,...,In} l'ensemble des intervalles de la droite réelle. Le graphe des Ensembles pour S est le graphe G=(V,A) ou V={v1,v2,...,vn} et l'adjacence se définit ainsi : vj est adjacent a vk ssi les ensembles Ij et Ik ne sont pas disjoints. On demande :
    a) Construire le graphe d'intervalles de {(0,2),(3,8),(1,4),(3,4),(2,5),(7,9)}
    b) Démontrer que Kn est un graphe d'ensembles pour tout n>0
    c) Démontrer que C4 n'est pas un graphe d'ensembles

    Merci d'avance !

    Pirokkk


Se connecter pour répondre