อ่าน 2 นาที
แผนที่การหมุน
ในทางคณิตศาสตร์แผนที่การหมุน (Rotation map) คือฟังก์ชันที่แสดงถึงกราฟแบบไม่มีทิศทางที่มีป้ายกำกับ ขอบ โดยที่แต่ละจุดยอดจะระบุเพื่อนบ้านที่ออกจากจุดยอดนั้น...
แผนที่การหมุน
ในทางคณิตศาสตร์แผนที่การหมุน (Rotation map) คือฟังก์ชันที่แสดงถึงกราฟแบบไม่มีทิศทางที่มีป้ายกำกับ ขอบ โดยที่แต่ละจุดยอดจะระบุเพื่อนบ้านที่ออกจากจุดยอดนั้น แผนที่การหมุนถูกนำเสนอครั้งแรกโดย Reingold, Vadhan และ Wigderson (“Entropy waves, the zig-zag graph product , and new constant-degree expanders”, 2002) เพื่อความสะดวกในการกำหนดผลคูณซิกแซก (zig-zag product ) และพิสูจน์คุณสมบัติของมัน เมื่อกำหนดจุดยอดและป้ายกำกับขอบแผนที่การหมุนจะส่งคืนเพื่อนบ้านลำดับที่ ของจุดยอดนั้นและป้ายกำกับขอบที่จะนำกลับไปยังจุดยอดนั้น
คำนิยาม
สำหรับกราฟG ที่เป็น D -regular แผนที่การหมุนจะถูกกำหนดดังนี้: ถ้า ขอบที่ iที่ออกจากvนำไปสู่wและขอบที่j ที่ออกจาก wนำไป สู่ v
คุณสมบัติพื้นฐาน
จากนิยาม เราจะเห็นว่าเป็นการเรียงสับเปลี่ยน และยิ่งไปกว่านั้น ยังเป็นการแมปเอกลักษณ์ ( เป็นการผกผัน )
กรณีพิเศษและคุณสมบัติพิเศษ
- แผนที่การหมุนจะมีป้ายกำกับที่สอดคล้องกันก็ต่อเมื่อขอบทั้งหมดที่ออกจากแต่ละจุดยอดมีป้ายกำกับในลักษณะที่ว่า ณ แต่ละจุดยอด ป้ายกำกับของขอบที่เข้ามาจะต้องแตกต่างกันทั้งหมดกราฟปกติ ทุกกราฟ จะมีป้ายกำกับที่สอดคล้องกันบางอย่าง
- แผนที่การหมุนที่สอดคล้องกันสามารถใช้ในการเข้ารหัสการเดินควอนตัมแบบ เวลาไม่ต่อเนื่องที่สร้างขึ้น บนกราฟ (ปกติ) ได้
- แผนที่การหมุนจะมีความสอดคล้องกันก็ต่อเมื่อจากนิยามแล้วแผนที่การหมุนที่มีความสอดคล้องกันจะต้องมีป้ายกำกับที่สอดคล้องกัน
ดูเพิ่มเติม
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ แผนที่การหมุน
ในทางคณิตศาสตร์แผนที่การหมุน (Rotation map) คือฟังก์ชันที่แสดงถึงกราฟแบบไม่มีทิศทางที่มีป้ายกำกับ ขอบ โดยที่แต่ละจุดยอดจะระบุเพื่อนบ้านที่ออกจากจุดยอดนั้น...
คำนิยาม
สำหรับกราฟ G ที่เป็น D -regular แผนที่การหมุนจะถูกกำหนดดังนี้: ถ้า ขอบที่ i ที่ออกจาก v นำไปสู่ w และขอบที่ j ที่ออกจาก w นำไป สู่ v อาร์ โอ ที จี : [ เอ็น ] × [ ดี ] → [ เอ็น ] × [ ดี ] {\displaystyle \mathrm {เน่า} _{G}:[N]\times [D]\rightarrow...
คุณสมบัติพื้นฐาน
จากนิยาม เราจะเห็นว่าเป็นการเรียงสับเปลี่ยน และยิ่งไปกว่านั้น ยังเป็นการแมปเอกลักษณ์ ( เป็นการ ผกผัน ) อาร์ โอ ที จี {\displaystyle \mathrm {เน่า} _{G}} อาร์ โอ ที จี ∘ อาร์ โอ ที จี {\displaystyle \mathrm {เน่า} _{G}\circ \mathrm {เน่า} _{G}} อาร์ โอ ที จี...
กรณีพิเศษและคุณสมบัติพิเศษ
แผนที่การหมุนจะมีป้ายกำกับที่สอดคล้องกันก็ต่อเมื่อขอบทั้งหมดที่ออกจากแต่ละจุดยอดมีป้ายกำกับในลักษณะที่ว่า ณ แต่ละจุดยอด ป้ายกำกับของขอบที่เข้ามาจะต้องแตกต่างกันทั้งหมด กราฟปกติ ทุกกราฟ จะมีป้ายกำกับที่สอดคล้องกันบางอย่าง...