การฝังกราฟไอโซมอร์ฟิกในอวกาศยุคลิด
ให้กราฟที่ไม่บอกทิศทางและไม่ถ่วงน้ำหนัก $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$ ในแบบที่คุณอธิบายต้องการให้ภาพของจุดยอดทั้งสี่เป็น coplanar สร้างรูปสี่เหลี่ยมจัตุรัส (เนื่องจากระยะห่างระหว่างจุดยอดที่อยู่ติดกันต้องเป็น $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)$, ความขัดแย้ง.