กราฟทรานสโพส

ในทฤษฎีกราฟ กราฟทรานสโพส (, ex. 22.1–3, p. 530. หรือ converse graph . หรือ reverse graph, entry 2.24, p. 275.) ของกราฟระบุทิศทาง G คือกราฟระบุทิศทางที่มีจุดยอดเช่นเดียวกับ G แต่เส้นเชื่อมทั้งหมดได้ถูกกลับทิศทาง กล่าวคือ หากกราฟ G มีเส้นเชื่อม (u,v) แล้ว กราฟทราสโพสของ G จะมีเส้นเชื่อม (v,u) แทน

 สัญกรณ์และชื่อเรียก 
คำว่า คอนเวิร์ส (converse) มาจากแนวคิดทางตรรกศาสตร์ที่ประพจน์ p → q มี converse คือ q → p ซึ่งก็คล้าย ๆ กับกรณีของกราฟทรานโพสที่เส้นเชื่อมจาก u → v ถูกกลับเป็น v → u

คำว่า ทรานโพส (transpose) มาจากการดำเนินการทรานสโพสบนเมทริกซ์ จากการที่เมทริกซ์ประชิดแทนกราฟทรานโพส คือทรานโพสของเมทริกซ์ประชิดแทนกราฟดั้งเดืม จึงเป็นที่มาของคำว่ากราฟทรานโพสนั่นเอง

ปัจจุบันนี้ ยังไม่มีข้อตกลงถึงศัพท์ที่ใช้เรียกกราฟทรานสโพสอย่างแน่นอน โดยในบทความนี้จะขอเรียกใช้คำว่า กราฟทรานสโพส

สัญกรณ์ของกราฟทรานโพสก็มีมากมายแตกต่างกันออกไป เช่น G''', GT, GR ขึ้นอยู่กับว่าในหนังสือหรือบทความนั้นกำหนดเรียกสัญกรณ์ของกราฟทรานโพสไว้ว่าอย่างไร

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

ในขั้นตอนวิธีกราฟ การสร้างกราฟทรานโพสจะเป็นการทำให้ได้กราฟที่เหมาะสมในการประมวลผลในบางปัญหามากกว่า และอาจช่วยในการดำเนินการหาคำตอบของขั้นตอนวิธีได้ ยกตัวอย่างเช่นการหาส่วนประกอบที่เชื่อมกันแบบเข้มของกราฟ G ด้วยขั้นตอนวิธีของโกสรชุ มีวิธีการคือทำการค้นในแนวลึกของกราฟ G'' จากนั้นก็ทำการค้นในแนวลึกของกราฟทรานโพสของ G อีกรอบ

 อ้างอิง 

หมวดหมู่:กราฟระบุทิศทาง
หมวดหมู่:การดำเนินการบนกราฟ