ユークリッド空間への同型グラフ埋め込み

Question

無向で重み付けされていないグラフが与えられた $G = (V, E)$、マッピングを見つけることは可能ですか？ $f: V \rightarrow \mathbb{R}^k$ いくつかのための $k$ そのようなすべてのために $i, j \in V$、 $\|f(i) - f(j)\|_2^2 = \Delta(i, j)$、 どこ $\Delta(i, j)$ 間の最短経路長です $i$ そして $j$ に $G$？

私はこれらの等尺性埋め込みのいくつかの反例をテストしてきました $\ell_2$ 存在しませんが（たとえば、4サイクル）、この場合は機能します。

Answer 1

これは一般的には不可能です。

4サイクルは実際に検討するのに役立ちます：それをに埋め込む $\mathbb{R}^k$ あなたが説明する方法では、4つの頂点すべての画像が同一平面上にあり、正方形を形成する必要があります（隣接する頂点間の距離は $1$ 隣接していないペア間のものは $\sqrt{2}$）。

ここで、完全2部グラフについて考えてみましょう。 $K_{2,3}$。その頂点を呼びましょう$a_1,a_2,b_1,b_2,b_3$。どんな埋め込みでも$f$ あなたの条件を満たす、4サイクル $(a_1,b_1,a_2,b_2)$、 $(a_1,b_1,a_2,b_3)$ そして $(a_1,b_2,a_2,b_3)$ 上記のようにすべてを正方形にマッピングする必要がありますが、これらの条件の最初の2つは $f(b_2) = f(b_3)$、矛盾。