Théorie des graphes



  • 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
 

Découvre aussi nos cours et fiches méthode par classe

Les cours pour chaque niveau

Progresse en maths avec Schoolmouv

Apprends, révise et progresse avec Schoolmouv

Encore plus de réponses par ici

Il semble que votre connexion ait été perdue, veuillez patienter pendant que nous vous re-connectons.