Discussion :

[HanLee]

Salut,

Mon frère n'arrive pas à résoudre la question suivante, et moi non plus.

Soit X un ensemble.
Une fonction k : X * X -> R est dite conditionnellement définie positive ssi elle est symétrique et vérifie :

Somme i,j = 1 à n ( ai.aj k(xi, xj) ) est supérieur ou égal à 0

pour tout entier n, x1, ... xn dans X et a1 ... an des réels quelconques tels que leur somme soit nulle.
---------------------------------

Montrée que la fonction "plus courte distance" dans un arbre est conditionnellement définie positive sur l'ensemble de ses noeuds.

On définit la plus courte distance entre 2 noeuds d'un arbre comme le nombre d'arêtes qui composent l'unique chemin qui les relie.

J'ai essayé en raisonnant par induction structurelle en raisonnant d'abord sur un arbre binaire, mais bon, j'ai pas réussi à faire des bonnes majorations, je les trouve super grossières, et au final j'ai rien.

Vous avez une idée ?

Merci d'avance.

[ToTo13]

Bonsoir,

il faut montrer que la fonction distance dans un arbre est symétrique et vérifie l'inégalité que tu as écrit.

1 - Une distance est par définition symmétrique !!! Donc la fonction "distance" dans un arbre est symmétrique. Si ça ne suffit pas, appuie toi sur la définition d'un arbre qui dit que le chemin le plus court entre deux noeuds d'un arbre est unique.
2 - Là j'ai un gros doute... Es tu sûr que ta définition est complète, car je pense qu'il doit manquer quelque chose. Prenons un exemple : soit A et B deux points différents de l'arbre, on a N=1 et on prend au hasard {-1,1} pour les aij. Comme k est une distance et que A et B sont différents, k(A,B) > 0, mais ai.aj < 0, donc la fonction est négative.
Sauf si on considère que la somme qui doit être positive ou nulle pour les ai, c'est la somme des composants des ai (ai={ai1, ai2, ... ain}). Auquel cas, il faut montrer que si la somme des ai est positive et que la somme des aj est aussi positive, alors la somme des ai.aj est positive. Mais là encore, j'ai un joli contre exemple : pour N=2, (a1=10, a2=1) et (b1=-1,b2=1) => a1.b1 + a2.b2 = -9.
Donc je pense que la définition ne doit pas être complète...

[HanLee]

Salut,

Oui le fait que la distance sur un arbre est symétrique c'était évident, la difficulté c'était le reste.

En fait, il y a peut-être une erreur dans l'énoncé, il faut peut-être considérer l'opposé de la distance entre 2 nœuds d'un arbre, parce que dans une question précédente, on démontre qu'il existe un espace de Hilbert H et une fonction Phi : X -> H telle que :

k(x,y) = -|| Phi(x) - Phi(y) ||² (norme associée au produit scalaire)

avec k conditionnellement définie positive.

Et là, ya moyen que ça marche.