Изоморфные вложения графов в евклидово пространство
Учитывая неориентированный и невзвешенный граф $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-х тактный), но в этом случае они работают.
Ответы
В общем случае это невозможно.
На самом деле полезно рассмотреть 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)$, противоречие.