Penyematan grafik isomorfik di Ruang Euclidean

Aug 19 2020

Diberikan grafik tidak terarah dan tidak berbobot $G = (V, E)$, apakah mungkin untuk menemukan pemetaan $f: V \rightarrow \mathbb{R}^k$ untuk beberapa $k$ seperti itu untuk setiap $i, j \in V$, $\|f(i) - f(j)\|_2^2 = \Delta(i, j)$, dimana $\Delta(i, j)$ adalah panjang jalur terpendek di antaranya $i$ dan $j$ di $G$?

Saya telah menguji beberapa contoh berlawanan yang memasukkan embeddings isometrik ini $\ell_2$ gagal untuk ada (misalnya, 4-siklus), tetapi dalam hal ini mereka berhasil.

Jawaban

12 KlausDraeger Aug 20 2020 at 01:53

Ini tidak mungkin secara umum.

4 siklus sebenarnya sangat membantu untuk dipertimbangkan: memasukkannya ke dalam $\mathbb{R}^k$ cara Anda mendeskripsikan membutuhkan gambar dari keempat simpul menjadi koplanar, membentuk persegi (karena jarak antara simpul yang berdekatan haruslah $1$ dan pasangan yang tidak bersebelahan harus berada $\sqrt{2}$).

Sekarang perhatikan grafik bipartit lengkap $K_{2,3}$. Mari kita sebut simpulnya$a_1,a_2,b_1,b_2,b_3$. Dalam penyematan apa pun$f$ memuaskan kondisi Anda, 4 siklus $(a_1,b_1,a_2,b_2)$, $(a_1,b_1,a_2,b_3)$ dan $(a_1,b_2,a_2,b_3)$ semua harus dipetakan ke kotak seperti di atas, tetapi dua kondisi pertama menyiratkan $f(b_2) = f(b_3)$, kontradiksi.