ใน สาขา คณิตศาสตร์ของทฤษฎีกราฟกราฟการเรียงสับเปลี่ยนคือกราฟที่มีจุดยอดแทนองค์ประกอบของการเรียงสับเปลี่ยนและขอบแทนคู่ขององค์ประกอบที่ถูกสลับตำแหน่งโดยการเรียงสับเปลี่ยน กราฟการเรียงสับเปลี่ยนยังสามารถกำหนดได้ในเชิงเรขาคณิตเช่นกราฟจุดตัดของส่วนของเส้นตรงที่มีจุดปลายอยู่บนเส้นขนานสองเส้นการเรียงสับเปลี่ยนที่แตกต่างกันอาจทำให้เกิดกราฟการเรียงสับเปลี่ยนเดียวกันได้ กราฟที่กำหนดจะมีรูปแบบการแสดงที่ไม่ซ้ำกัน (โดยคำนึงถึงสมมาตร ของการเรียงสับเปลี่ยน ) หากเป็นจำนวนเฉพาะเมื่อเทียบกับการแยกส่วนแบบโมดูลาร์^{[ 1 ]}

ถ้าเป็นการเรียงสับเปลี่ยน ใดๆ ของตัวเลขตั้งแต่ถึงแล้วเราสามารถกำหนดกราฟการเรียงสับเปลี่ยนจาก ได้โดยที่ มีจุดยอดและ มีเส้นเชื่อมสำหรับดัชนีสองตัวใดๆที่ปรากฏก่อนในนั่นคือ ดัชนีสองตัวและกำหนดเส้นเชื่อมในกราฟการเรียงสับเปลี่ยนได้ก็ต่อเมื่อดัชนีทั้งสองนั้นกำหนดการผกผันในการเรียงสับเปลี่ยน ${\displaystyle \rho =(\sigma _{1},\sigma _{2},...,\sigma _{n})}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle \sigma }$${\displaystyle n}$${\displaystyle v_{1},v_{2},...,v_{n}}$${\displaystyle v_{i}v_{j}}$${\displaystyle i<j}$${\displaystyle j}$${\displaystyle i}$${\displaystyle \rho }$${\displaystyle i}$${\displaystyle j}$

เมื่อกำหนดการเรียงสับเปลี่ยนแล้วเราอาจกำหนดเซตของส่วนของเส้นตรงที่มีจุดปลายอยู่ที่และได้เช่นกัน โดยที่ จุดปลายของส่วนของเส้นตรงเหล่านี้อยู่บนเส้นตรงขนานสองเส้นคือ และและส่วนของเส้นตรงสองเส้นจะมีจุดตัดที่ไม่ว่างเปล่าก็ต่อเมื่อจุดตัดเหล่านั้นสอดคล้องกับการผกผันในการเรียงสับเปลี่ยน ดังนั้น กราฟการเรียงสับเปลี่ยนของจึงตรงกับกราฟจุดตัดของส่วนของเส้นตรง สำหรับเส้นตรงขนานสองเส้นใดๆ และเซตจำกัดของส่วนของเส้นตรงที่มีจุดปลายอยู่บนเส้นตรงทั้งสองเส้น กราฟจุดตัดของส่วนของเส้นตรงจะเป็นกราฟการเรียงสับเปลี่ยน ในกรณีที่จุดปลายของส่วนของเส้นตรงทั้งหมดแตกต่างกัน การเรียงสับเปลี่ยนที่ทำให้กราฟจุดตัดนี้เป็นกราฟการเรียงสับเปลี่ยนอาจกำหนดได้โดยการกำหนดหมายเลขให้กับส่วนของเส้นตรงบนเส้นตรงเส้นใดเส้นหนึ่งตามลำดับ และอ่านหมายเลขเหล่านี้ตามลำดับที่จุดปลายของส่วนของเส้นตรงปรากฏบนเส้นตรงอีกเส้นหนึ่ง ${\displaystyle \sigma }$${\displaystyle s_{i}}$${\displaystyle (i,0)}$${\displaystyle (k,1)}$${\displaystyle \sigma _{k}=i}$${\displaystyle y=0}$${\displaystyle y=1}$${\displaystyle \sigma }$

กราฟการเรียงสับเปลี่ยนมีลักษณะเฉพาะที่เทียบเท่ากันอีกหลายประการ:

• กราฟจะเป็นกราฟการเรียงสับเปลี่ยนก็ต่อเมื่อเป็นกราฟวงกลมที่ยอมรับเส้นศูนย์สูตร กล่าว คือเส้นคอร์ด เพิ่มเติม ที่ตัดกับเส้นคอร์ดอื่นทุกเส้น^{[ 2 ]}${\displaystyle G}$${\displaystyle G}$
• กราฟจะเป็นกราฟการเรียงสับเปลี่ยนก็ต่อเมื่อทั้งกราฟและกราฟส่วนเติมเต็มเป็นกราฟเปรียบเทียบ^{[ 3 ]}${\displaystyle G}$${\displaystyle G}$${\displaystyle {\overline {G}}}$
• กราฟจะเป็นกราฟการเรียงสับเปลี่ยนก็ต่อเมื่อเป็นกราฟเปรียบเทียบของเซตที่มีลำดับบางส่วนซึ่งมีมิติลำดับไม่เกินสอง^{[ 4 ]}${\displaystyle G}$
• ถ้ากราฟหนึ่งเป็นกราฟการเรียงสับเปลี่ยน กราฟส่วนเติมเต็มของมันก็เป็นกราฟการเรียงสับเปลี่ยนเช่นกัน การเรียงสับเปลี่ยนที่แสดงถึงส่วนเติมเต็มของกราฟหนึ่งอาจได้มาจากการกลับการเรียงสับเปลี่ยนที่แสดงถึงกราฟอีกกราฟหนึ่ง${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$

เป็นไปได้ที่จะทดสอบว่ากราฟที่กำหนดเป็นกราฟการเรียงสับเปลี่ยนหรือไม่ และถ้าเป็นเช่นนั้น ให้สร้างการเรียงสับเปลี่ยนที่แสดงถึงกราฟนั้นในเวลาเชิงเส้น^{[ 5 ]}

เนื่องจากกราฟการเรียงสับเปลี่ยนเป็นกลุ่มย่อยของกราฟสมบูรณ์ปัญหาหลายอย่างที่เป็นปัญหาNP-completeสำหรับกราฟใดๆ อาจสามารถแก้ไขได้อย่างมีประสิทธิภาพสำหรับกราฟการเรียงสับเปลี่ยน ตัวอย่างเช่น:

• กลุ่มที่ใหญ่ที่สุดในกราฟการเรียงสับเปลี่ยนจะสอดคล้องกับลำดับย่อยที่ลดลงยาวที่สุดในการเรียงสับเปลี่ยนที่กำหนดกราฟ ดังนั้นปัญหากลุ่มอาจได้รับการแก้ไขในเวลาพหุนามสำหรับกราฟการเรียงสับเปลี่ยนโดยใช้อัลกอริทึมลำดับย่อยที่ลดลงยาวที่สุด^{[ 6 ]}
• ในทำนองเดียวกัน ลำดับย่อยที่เพิ่มขึ้นในลำดับการเรียงสับเปลี่ยนจะสอดคล้องกับเซตอิสระที่มีขนาดเท่ากันในกราฟการเรียงสับเปลี่ยนที่เกี่ยวข้อง
• ความกว้างของต้นไม้และความกว้างของเส้นทางของกราฟการเรียงสับเปลี่ยนสามารถคำนวณได้ในเวลาพหุนาม อัลกอริทึมเหล่านี้ใช้ประโยชน์จากข้อเท็จจริงที่ว่าจำนวนตัวคั่นจุดยอดขั้นต่ำของการรวมในกราฟการเรียงสับเปลี่ยนเป็นพหุนามตามขนาดของกราฟ^{[ 7 ]}

กราฟการเรียงสับเปลี่ยนเป็นกรณีพิเศษของกราฟวงกลมกราฟเปรียบเทียบ กราฟส่วนเติมเต็มของกราฟเปรียบเทียบ และกราฟ สี่เหลี่ยมคางหมู

กลุ่มย่อยของกราฟการเรียงสับเปลี่ยน ได้แก่ กราฟการเรียงสับเปลี่ยน แบบสองส่วน (ซึ่งอธิบายลักษณะโดยSpinrad, Brandstädt & Stewart ในปี 1987 ) และโค กราฟ

• "กราฟการเรียงสับเปลี่ยน"ระบบสารสนเทศเกี่ยวกับคลาสของกราฟและการรวมเข้าด้วยกัน
• ไวส์สไตน์, เอริค ดับเบิลยู. , "กราฟการเรียงสับเปลี่ยน" , MathWorld