Bonsoir
dans un graphe G ne contennat pas de K2,s
soit S un ensemble de n points du plan R2, muni de la distance euclidienne d. Montrer que, pour n assez grand, le nombre de paires {a,b}, qui ont un voisin commun tq d(a,b)=1 ,est inférieur à n3/2.
Je ne comprends pas grand chose à cette question
pourriez-vous me l'expliquer
on me conseille de dire si le graphe peut contenir K2,3
et d'utiliser le résultat
m<= [n/4 (1+ (4(s-1) (n-1)+1)1/2]
merci pour votre aide
fifrelette
Exprimée comme ça, cette question ne veut rien dire en effet. Que signifie "une paire {a,b} ayant un voisin commun" ? Que vient faire le "dans un graphe ne contenant pas de K₂,s" au début alors que tu n'en parles plus après ? Il doit manquer quelque chose...
P.S.: Peut-être pourrais-tu recopier exactement l'énoncé pour qu'on puisse t'aider !
bonjour
merci pour la réponse,
en effet, j'étais fatiguée et c'est pas clair
la paireb {a,b} est élément de P2 (S): {u,v}élément de A et {u,w}élément de A
où A est l'ensemble des arêtes et u,w et v des sommets
Ce qui me bloque c'est d(a,b)=1, je ne comprends pas ce que ça veut dire
alors je bn'arrives pas à comprendre pourquoi les paires {a,b}élélde P2(S) <=n3/2
fifrelette
