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

จากวิกิพีเดีย สารานุกรมเสรี

ในทฤษฎีกราฟ กราฟทรานสโพส (อังกฤษ: transpose graph[1] หรือ converse graph [2] หรือ reverse graph[3]) ของกราฟระบุทิศทาง G คือกราฟระบุทิศทางที่มีจุดยอดเช่นเดียวกับ G แต่เส้นเชื่อมทั้งหมดได้ถูกกลับทิศทาง กล่าวคือ หากกราฟ G มีเส้นเชื่อม (u,v) แล้ว กราฟทราสโพสของ G จะมีเส้นเชื่อม (v,u) แทน

สัญกรณ์และชื่อเรียก[แก้]

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

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

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

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

การนำมาใช้งาน[แก้]

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

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

อ้างอิง[แก้]

  1. Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L.. Introduction to Algorithms. MIT Press and McGraw-Hill.  , ex. 22.1–3, p. 530.
  2. Harary, Frank; Norman, Robert Z.; Cartwright, Dorwin (1965), Structural Models: An Introduction to the Theory of Directed Graphs, New York: Wiley .
  3. 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.