กราฟทรานสโพส
ในทฤษฎีกราฟ กราฟทรานสโพส (อังกฤษ: transpose graph[1] หรือ converse graph [2] หรือ reverse graph[3]) ของกราฟระบุทิศทาง 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 อีกรอบ
อ้างอิง[แก้]
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. Introduction to Algorithms. MIT Press and McGraw-Hill., ex. 22.1–3, p. 530.
- ↑ Harary, Frank; Norman, Robert Z.; Cartwright, Dorwin (1965), Structural Models: An Introduction to the Theory of Directed Graphs, New York: Wiley.
- ↑ Essam, John W.; Fisher, Michael E. (1970), "Some basic definitions in graph theory", Review of Modern Physics, 42 (2): 271–288, doi:10.1103/RevModPhys.42.271, entry 2.24, p. 275.