แผนที่เชิงคอมบินาทอริกคือ การแสดง เชิงคอมบินาทอริกของกราฟบนพื้นผิวที่กำหนดทิศทางได้แผนที่เชิงคอมบินาทอริกอาจเรียกว่าการฝังเชิงคอม บินาทอ ริกระบบการหมุนกราฟริบ บอน ที่กำหนดทิศทางได้กราฟอ้วน หรือกราฟวัฏจักร^{[ 1 ]}โดยทั่วไปแล้วแผนที่เชิงคอมบินาทอริกมิติ คือการแสดงเชิงคอมบินาทอริกของกราฟบนแมนิโฟลด์ที่กำหนดทิศทางได้มิติ ${\displaystyle n}$${\displaystyle n}$

แผนที่เชิงการจัดเรียง (Combinatorial map) ถูกใช้เป็นโครงสร้างข้อมูลที่มีประสิทธิภาพในการแสดงและประมวล ผลภาพ รวมถึงการสร้างแบบจำลองทางเรขาคณิต แบบจำลองนี้เกี่ยวข้องกับคอมเพล็กซ์เชิงซิมพลิเชียล (simplicial complexes ) และโทโพโลยีเชิงการจัดเรียง แผนที่เชิงการจัดเรียงเป็น แบบจำลอง การแสดงขอบเขตโดยจะแสดงวัตถุด้วยขอบเขตของมัน

แนวคิดของแผนที่เชิงการจัดเรียงได้รับการแนะนำอย่างไม่เป็นทางการโดยJ. Edmondsสำหรับพื้นผิวทรงหลายเหลี่ยม^{[ 2 ]}ซึ่งเป็นกราฟระนาบมีการกำหนดรูปแบบอย่างเป็นทางการครั้งแรกภายใต้ชื่อ "กลุ่มดาว" โดย A. Jacques ^{[ 3 ] [ 4 ]}แต่แนวคิดนี้ถูกนำไปใช้อย่างกว้างขวางแล้วภายใต้ชื่อ "การหมุน" โดยGerhard Ringel ^{[ 5 ]}และ JWT Youngs ในวิธีแก้ปัญหาการระบายสีแผนที่ Heawood ที่มีชื่อเสียง คำว่า "กลุ่มดาว" ไม่ได้ถูกนำมาใช้ต่อ และคำว่า "แผนที่เชิงการจัดเรียง" ได้รับความนิยมมากกว่า^{[ 6 ]}

ต่อมา แผนที่เชิงการจัดเรียง (Combinatorial maps) ได้ถูกขยายขอบเขตให้ครอบคลุมถึงการแสดงวัตถุที่แบ่งย่อยและสามารถกำหนดทิศทางได้ในมิติที่สูงขึ้น

แอปพลิเคชันหลายอย่างต้องการโครงสร้างข้อมูลเพื่อแสดงการแบ่งย่อยของวัตถุ ตัวอย่างเช่น วัตถุ 2 มิติสามารถแบ่งออกเป็นจุดยอด (เซลล์ 0) ขอบ (เซลล์ 1) และหน้า (เซลล์ 2) โดยทั่วไปแล้ว วัตถุ n มิติจะประกอบด้วยเซลล์ที่มีมิติ 0 ถึง n นอกจากนี้ ยังมักจำเป็นต้องแสดงความสัมพันธ์ระหว่างเซลล์ข้างเคียงเหล่านี้ด้วย

ดังนั้น เราต้องการอธิบายเซลล์ทั้งหมดของการแบ่งย่อย รวมทั้งความสัมพันธ์ของการเกิดและการอยู่ติดกันระหว่างเซลล์เหล่านั้น เมื่อเซลล์ที่แสดงทั้งหมดเป็นซิมเพล็กซ์ เรา อาจใช้ คอมเพล็กซ์ซิมพลิเชียลได้ แต่เมื่อเราต้องการแสดงเซลล์ประเภทใดก็ตาม เราจำเป็นต้องใช้แบบจำลองทางโทโพโลยีแบบเซลล์ เช่น แผนที่เชิงการจัดเรียง หรือแผนที่ทั่วไป

แผนที่เชิงการจัดเรียง (Combinatorial map) คือสามสิ่งM  = ( D ,  σ ,  α )ซึ่งมีคุณสมบัติดังนี้:

• Dคือเซตของลูกดอกที่มีจำนวนจำกัด
• σคือการเรียงสับเปลี่ยนบน D ;
• αคืออินโวลูชันบน Dที่ไม่มีจุดตรึง

โดยสัญชาตญาณแล้ว แผนที่เชิงการจัดเรียง (combinatorial map) สอดคล้องกับกราฟที่แต่ละขอบถูกแบ่งออกเป็นสองลูกศร (บางครั้งเรียกว่าขอบครึ่ง) การเรียงสับเปลี่ยนσจะให้ลูกศรถัดไปสำหรับแต่ละลูกศร โดยการหมุนจุดยอดไปในทิศทางบวก ในขณะที่การเรียงสับเปลี่ยนอีกแบบαจะให้ลูกศรอีกอันของขอบเดียวกันสำหรับแต่ละลูกศร

αช่วยให้สามารถดึงขอบ ( αแทน rêteในภาษาฝรั่งเศส) และ σช่วยให้สามารถดึงจุดยอด ( σแทน sommetในภาษาฝรั่งเศส) เรากำหนด φ  =  σ ∘ αซึ่งจะให้จุดยอดถัดไปของหน้าเดียวกัน ( phiแทนface ในภาษาฝรั่งเศส) สำหรับแต่ละ ลูก ศร

ดังนั้น จึงมีสองวิธีในการแสดงแผนที่เชิงการจัดเรียง ขึ้นอยู่กับว่าการเรียงสับเปลี่ยนคือσหรือφ (ดูตัวอย่างด้านล่าง) การแสดงทั้งสองแบบนี้เป็นแบบคู่กัน กล่าวคือ จุดยอดและหน้าจะสลับกัน

ตัวอย่างแผนที่เชิงการจัดเรียง : กราฟระนาบและแผนที่เชิงการจัดเรียงสองแบบ ขึ้นอยู่กับว่าเราใช้สัญลักษณ์( D ,  σ ,  α )หรือ( D ,  φ ,  α )

แผนที่ เชิงการจัดเรียงแบบ nมิติ (หรือ แผนที่ n มิติ ) คือทูเปิล ( n  + 1) M  = ( D ,  β ₁ , ...,  β _n )เช่นนั้น: ^{[ 7 ] [ 8 ]}

• Dคือเซตของลูกดอกที่มีจำนวนจำกัด
• β ₁คือการเรียงสับเปลี่ยนบน D ;
• β ₂ , ... ,  β _nเกี่ยวข้องกับD ;
• β _i  ∘  β _jเป็นอินโวลูชัน ถ้าi +  2 ≤  j ( i ,  j ∈ { 1, ,...,  n  })

แผนที่ เชิงการจัดเรียงแบบ nมิติ แสดงถึงการแบ่งย่อยของ ปริภูมิ nมิติแบบปิดที่สามารถกำหนดทิศทางได้ ข้อจำกัดบนβ _i  ∘  β _jรับประกันความถูกต้องทางโทโพโลยีของแผนที่ในฐานะการแบ่งย่อยของกึ่งแมนิโฟลด์ แผนที่เชิงการจัดเรียงแบบสองมิติสามารถเรียกคืนได้โดยการกำหนดค่าn  = 2และเปลี่ยนชื่อ σเป็นβ ₁และαเป็นβ ₂

พื้นที่ที่ไม่จำเป็นต้องเป็นพื้นที่ปิดหรือสามารถกำหนดทิศทางได้อาจแสดงได้โดยใช้แผนที่ทั่วไป ( nมิติ)

ในคณิตศาสตร์เชิง การจัดเรียง ระบบการหมุน ( เรียกอีกอย่างว่าการฝังเชิงการจัดเรียงหรือแผนที่เชิงการจัดเรียง ) เข้ารหัสการฝังของกราฟลงบนพื้นผิวที่สามารถกำหนดทิศทางได้โดยการอธิบายลำดับวงกลมของ ขอบของ กราฟรอบแต่ละจุดยอด คำจำกัดความที่เป็นทางการมากขึ้นของระบบการหมุนเกี่ยวข้องกับคู่ของการเรียงสับเปลี่ยนคู่ดังกล่าวเพียงพอที่จะกำหนดมัลติกราฟพื้นผิว และการฝังแบบ 2 เซลล์ของมัลติกราฟลงบนพื้นผิวได้

แผนการหมุนแต่ละแบบกำหนดการฝัง 2 เซลล์ที่ไม่ซ้ำกันของ มัลติกราฟ ที่เชื่อมต่อกันบนพื้นผิวปิดที่มีทิศทาง (โดยคำนึงถึงความสมมูลทางโทโพโลยีที่รักษาทิศทาง) ในทางกลับกัน การฝังมัลติกราฟที่เชื่อมต่อกันGบนพื้นผิวปิดที่มีทิศทางใดๆ จะกำหนดระบบการหมุนที่ไม่ซ้ำกันซึ่งมีGเป็นมัลติกราฟพื้นฐาน ความสมมูลพื้นฐานระหว่างระบบการหมุนและการฝัง 2 เซลล์นี้ได้รับการกำหนดในรูปแบบคู่เป็นครั้งแรกโดย Lothar Heffter ในช่วงทศวรรษ 1890 ^{[ 9 ]}และถูกนำไปใช้อย่างกว้างขวางโดยRingelในช่วงทศวรรษ 1950 ^{[ 10 ]}ในขณะเดียวกันEdmondsได้ให้รูปแบบดั้งเดิมของทฤษฎีบท^{[ 11 ]}และรายละเอียดของการศึกษาของเขาได้รับการเผยแพร่โดย Youngs ^{[ 12 ]} การวางนัยทั่วไปสำหรับมัลติกราฟได้รับการนำเสนอโดย Gross และ Alpert ^{[ 13 ]}

ระบบการหมุนมีความเกี่ยวข้อง แต่ไม่เหมือนกับแผนที่การหมุนที่ Reingold et al. (2002) ใช้ในการกำหนดผลคูณแบบซิกแซกของกราฟ ระบบการหมุนระบุลำดับวงกลมของขอบรอบแต่ละจุดยอด ในขณะที่แผนที่การหมุนระบุการเรียงสับเปลี่ยน (ที่ไม่ใช่แบบวงกลม) ของขอบที่แต่ละจุดยอด นอกจากนี้ ระบบการหมุนสามารถกำหนดได้สำหรับกราฟใดๆ ในขณะที่แผนที่การหมุนตามที่ Reingold et al. กำหนดนั้นจำกัดอยู่เฉพาะกราฟปกติเท่านั้น

ตามสูตรของออยเลอร์เราสามารถอนุมานจีนัสgของพื้นผิวปิดที่กำหนดทิศทางได้ซึ่งกำหนดโดยระบบการหมุน(นั่นคือ พื้นผิวที่มัลติกราฟพื้นฐานฝังตัวแบบ 2 เซลล์) ^{[ 14 ]}โปรดสังเกตว่าและเราพบว่า ${\displaystyle (\sigma ,\theta )}$${\displaystyle V=|Z(\sigma )|}$${\displaystyle E=|Z(\ทีต้า )|}$${\displaystyle F=|Z(\sigma \theta )|}$

${\displaystyle g=1-{\frac {1}{2}}(V-E+F)=1-{\frac {1}{2}}(|Z(\sigma )|-|Z(\theta )|+|Z(\sigma \theta )|)}$

โดยที่หมายถึงเซตของวงโคจรของการเรียงสับเปลี่ยน ${\displaystyle Z(\phi )}$${\displaystyle \phi }$

• พหุนามโบลโลบาส-ริออร์แดน
• การแสดงขอบเขต
• แผนที่ทั่วไป
• รายการขอบที่เชื่อมต่อสองทาง
• โครงสร้างข้อมูลขอบสี่เหลี่ยม
• ระบบการหมุน
• คอมเพล็กซ์ซิมพลิเชียล
• ขอบปีก

• แผนที่เชิงการจัดเรียงในCGALซึ่งเป็นไลบรารีอัลกอริทึมเรขาคณิตเชิงคำนวณ:
  • ดามิองด์, กิโยม. "แผนที่เชิงการจัดเรียง" . สืบค้นเมื่อ6 กุมภาพันธ์ 2021 .

• แผนที่เชิงการจัดเรียงในCGoGN , การสร้างแบบ จำลอง เชิงการจัดเรียงและเชิงเรขาคณิตด้วยแผนที่ทั่วไปNมิติ
• แผนที่เชิงการจัดเรียงที่ห้องปฏิบัติการn