กลับไปหน้าบทความ

อ่าน 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

คุณสมบัติพื้นฐาน

จากนิยาม เราจะเห็นว่าเป็นการเรียงสับเปลี่ยน และยิ่งไปกว่านั้น ยังเป็นการแมปเอกลักษณ์ ( เป็นการผกผัน )

กรณีพิเศษและคุณสมบัติพิเศษ

  • แผนที่การหมุนจะมีป้ายกำกับที่สอดคล้องกันก็ต่อเมื่อขอบทั้งหมดที่ออกจากแต่ละจุดยอดมีป้ายกำกับในลักษณะที่ว่า ณ แต่ละจุดยอด ป้ายกำกับของขอบที่เข้ามาจะต้องแตกต่างกันทั้งหมดกราฟปกติ ทุกกราฟ จะมีป้ายกำกับที่สอดคล้องกันบางอย่าง
  • แผนที่การหมุนที่สอดคล้องกันสามารถใช้ในการเข้ารหัสการเดินควอนตัมแบบ เวลาไม่ต่อเนื่องที่สร้างขึ้น บนกราฟ (ปกติ) ได้
  • แผนที่การหมุนจะมีความสอดคล้องกันก็ต่อเมื่อจากนิยามแล้วแผนที่การหมุนที่มีความสอดคล้องกันจะต้องมีป้ายกำกับที่สอดคล้องกัน

ดูเพิ่มเติม

ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Rotation_map&oldid=1345587815 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ แผนที่การหมุน

ในทางคณิตศาสตร์แผนที่การหมุน (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}} อาร์ โอ ที จี...

กรณีพิเศษและคุณสมบัติพิเศษ

แผนที่การหมุนจะมีป้ายกำกับที่สอดคล้องกันก็ต่อเมื่อขอบทั้งหมดที่ออกจากแต่ละจุดยอดมีป้ายกำกับในลักษณะที่ว่า ณ แต่ละจุดยอด ป้ายกำกับของขอบที่เข้ามาจะต้องแตกต่างกันทั้งหมด กราฟปกติ ทุกกราฟ จะมีป้ายกำกับที่สอดคล้องกันบางอย่าง...