ในทฤษฎีกราฟกราฟทรานสโพส (อังกฤษ: transpose graph หรือ converse graph หรือ reverse graph) ของกราฟระบุทิศทางG คือกราฟระบุทิศทางที่มีจุดยอดเช่นเดียวกับ G แต่เส้นเชื่อมทั้งหมดได้ถูกกลับทิศทาง กล่าวคือ หากกราฟ G มีเส้นเชื่อม (u,v) แล้ว กราฟทราสโพสของ G จะมีเส้นเชื่อม (v,u) แทน
สัญกรณ์และชื่อเรียก
คำว่า คอนเวิร์ส (converse) มาจากแนวคิดทางตรรกศาสตร์ที่ประพจน์ p → q มี converse คือ q → p ซึ่งก็คล้าย ๆ กับกรณีของกราฟทรานโพสที่เส้นเชื่อมจาก u → v ถูกกลับเป็น v → u
ในขั้นตอนวิธีกราฟ การสร้างกราฟทรานโพสจะเป็นการทำให้ได้กราฟที่เหมาะสมในการประมวลผลในบางปัญหามากกว่า และอาจช่วยในการดำเนินการหาคำตอบของขั้นตอนวิธีได้ ยกตัวอย่างเช่นการหาส่วนประกอบที่เชื่อมกันแบบเข้มของกราฟ 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.
สิงหาคม 04, 2021
กราฟทรานสโพส, ในทฤษฎ, กราฟ, งกฤษ, transpose, graph, หร, converse, graph, หร, reverse, graph, ของกราฟระบ, ศทาง, อกราฟระบ, ศทางท, ดยอดเช, นเด, ยวก, แต, เส, นเช, อมท, งหมดได, กกล, บท, ศทาง, กล, าวค, หากกราฟ, เส, นเช, อม, แล, กราฟทราสโพสของ, จะม, เส, นเช, อม, แทนส. inthvsdikraf krafthransophs xngkvs transpose graph 1 hrux converse graph 2 hrux reverse graph 3 khxngkrafrabuthisthang G khuxkrafrabuthisthangthimicudyxdechnediywkb G aetesnechuxmthnghmdidthukklbthisthang klawkhux hakkraf G miesnechuxm u v aelw krafthrasophskhxng G camiesnechuxm v u aethnsykrnaelachuxeriyk aekikhkhawa khxnewirs converse macakaenwkhidthangtrrksastrthipraphcn p q mi converse khux q p sungkkhlay kbkrnikhxngkrafthranophsthiesnechuxmcak u v thukklbepn v ukhawa thranophs transpose macakkardaeninkarthransophsbnemthriks cakkarthiemthriksprachidaethnkrafthranophs khuxthranophskhxngemthriksprachidaethnkrafdngedum cungepnthimakhxngkhawakrafthranophsnnexngpccubnni yngimmikhxtklngthungsphththiicheriykkrafthransophsxyangaennxn odyinbthkhwamnicakhxeriykichkhawa krafthransophssykrnkhxngkrafthranophskmimakmayaetktangknxxkip echn G GT GR khunxyukbwainhnngsuxhruxbthkhwamnnkahnderiyksykrnkhxngkrafthranophsiwwaxyangirkarnamaichngan aekikhthungaemwainthangkhnitsastr krafthranophs kbkrafdngedimcamikhwamaetktangknnxymakcnimminyyasakhy aetinwithyakarkhxmphiwetxrnn krafthranophsthuxwamikhwamaetktangcakkrafdngedimmak echnewbkraf sungepnkrafkhwamsmphnthkhxngkarlingkoynghnaipmarahwangewbtang casamarthhaesnechuxmxxkcakcudyxdid nnkhuxsamarthhaewbthihnadngklawoyngip idxyangngayday aetsahrbkaresnechuxmthiekhamayngcudyxdid nnkhuxhalingkthioyngekhamaynghnaid klbthaidlabakying cungthaihyaktxkarsrangkrafthranophsdwyechnkninkhntxnwithikraf karsrangkrafthranophscaepnkarthaihidkrafthiehmaasminkarpramwlphlinbangpyhamakkwa aelaxacchwyinkardaeninkarhakhatxbkhxngkhntxnwithiid yktwxyangechnkarhaswnprakxbthiechuxmknaebbekhmkhxngkraf G dwykhntxnwithikhxngoksrchu miwithikarkhuxthakarkhninaenwlukkhxngkraf G caknnkthakarkhninaenwlukkhxngkrafthranophskhxng G xikrxbxangxing aekikh 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 ekhathungcak https th wikipedia org w index php title krafthransophs amp oldid 4698198, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
