Plongements de graphes isomorphes dans l'espace euclidien
Étant donné un graphe non orienté et non pondéré$G = (V, E)$, est-il possible de trouver une cartographie$f: V \rightarrow \mathbb{R}^k$pour certains$k$telle que pour chaque$i, j \in V$,$\|f(i) - f(j)\|_2^2 = \Delta(i, j)$, où$\Delta(i, j)$est le chemin le plus court entre$i$et$j$dans$G$?
J'ai testé quelques contre-exemples pour lesquels ces plongements isométriques dans$\ell_2$n'existent pas (par exemple, le 4-cycle), mais dans ce cas, ils fonctionnent.
Réponses
Ce n'est pas possible en général.
Le 4-cycle est en fait utile à considérer : l'intégrer dans$\mathbb{R}^k$de la manière que vous décrivez nécessite que les images des quatre sommets soient coplanaires, formant un carré (puisque les distances entre les sommets adjacents doivent être$1$et ceux entre les paires non adjacentes doivent être$\sqrt{2}$).
Considérons maintenant le graphe biparti complet$K_{2,3}$. Appelons ses sommets$a_1,a_2,b_1,b_2,b_3$. Dans tout encastrement$f$satisfaisant votre condition, les 4 cycles$(a_1,b_1,a_2,b_2)$,$(a_1,b_1,a_2,b_3)$et$(a_1,b_2,a_2,b_3)$devraient tous être mappés sur des carrés comme ci-dessus, mais les deux premières de ces conditions impliquent$f(b_2) = f(b_3)$, contradiction.