유클리드 공간의 동형 그래프 임베딩

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$ 설명하는 방식에서 네 정점의 이미지는 모두 동일 평면에 있어야 정사각형을 형성합니다 (인접한 정점 사이의 거리는 $1$ 인접하지 않은 쌍 사이의 항목은 $\sqrt{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)$ 위와 같이 모두 사각형에 매핑되어야하지만 이러한 조건 중 처음 두 개는 $f(b_2) = f(b_3)$, 모순.