|
|
 |
Théorie des graphes |
| |
|
|
Envoyé: 27.02.2008, 23:00
|
enregistré depuis: févr.. 2008
Messages: 1
Status: hors ligne
dernière visite: 27.02.08
|
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
|
|
|
|
| |
|
|
| Boîte de connexion |
 Bienvenue invité
Inscris-toi c'est gratuit !
 
Rejoins-nous afin de poser tes questions dans les forums de Math foru' :
 Crée ton compte | | | |  Connexion :
|
| | | | | | | | |  | Membres |  | Nouveaux aujourd'hui | 2 | | | Nouveaux hier | 6 | | | Total | 9135 | | | Dernier | | Nc_Soft |
|
|
| |
|
