Théorie des graphes
-
Ppirokkk dernière édition par
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'ensemblesMerci d'avance !
Pirokkk