ใน สาขา คณิตศาสตร์ของทฤษฎีกราฟการลดรูปเชิงถ่ายทอด (Transitive Reduction ) ของกราฟทิศทางDคือกราฟทิศทางอีกกราฟหนึ่งที่มีจุดยอด เดียวกัน และมีขอบน้อยที่สุดเท่าที่จะเป็นไปได้ โดยที่สำหรับทุกคู่ จุดยอด vและw เส้นทาง (ทิศทาง) จากvไปยังwในDจะมีอยู่ก็ต่อเมื่อมีเส้นทางดังกล่าวอยู่ในกราฟที่ลดรูปแล้ว การลดรูปเชิงถ่ายทอดนี้ได้รับการแนะนำโดยAho, Garey & Ullman (1972)ซึ่งได้ให้ขอบเขตที่แน่นหนาเกี่ยวกับความซับซ้อนในการคำนวณของการสร้างกราฟเหล่านี้

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

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

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

การลดรูปเชิงถ่ายทอดสามารถกำหนดได้สำหรับความสัมพันธ์ทวิภาคเชิง นามธรรม บนเซตโดยการตีความคู่ของความสัมพันธ์นั้นเป็นส่วนโค้งในกราฟแบบมีทิศทาง

การลดรูปเชิงถ่ายทอด (Transitive Reduction) ของกราฟทิศทาง จำกัด Gคือกราฟที่มีจำนวนขอบน้อยที่สุดเท่าที่จะเป็นไปได้ ซึ่งมี ความสัมพันธ์ ในการเข้าถึงได้เหมือนกับกราฟเดิม กล่าวคือ ถ้ามีเส้นทางจากจุดยอดxไปยังจุดยอดyในกราฟGก็จะต้องมีเส้นทางจากxไปยังyในการลดรูปเชิงถ่ายทอดของGด้วย และในทางกลับกัน โดยเฉพาะอย่างยิ่ง ถ้ามีเส้นทางจาก x ไปยัง y และอีกเส้นทางหนึ่งจาก y ไปยัง z ก็อาจไม่มีขอบโดยตรงจาก x ไปยัง z ในการลดรูปเชิงถ่ายทอด ความเป็นถ่ายทอดสำหรับ x, y และ z หมายความว่า ถ้า x < y และ y < z แล้ว x < z ถ้าสำหรับเส้นทางใดๆ จาก y ไปยัง z มีเส้นทางจาก x ไปยัง y แล้วจะมีเส้นทางจาก x ไปยัง z ด้วย อย่างไรก็ตาม ไม่เป็นความจริงที่ว่าสำหรับเส้นทางใดๆ จาก x ไป y และจาก x ไป z จะมีเส้นทางจาก y ไป z ด้วย ดังนั้น ขอบใดๆ ระหว่างจุดยอด x และ z จึงถูกยกเว้นภายใต้การลดรูปเชิงถ่ายทอด เนื่องจากขอบเหล่านั้นแสดงถึงเส้นทางเดินที่ไม่เป็นเชิงถ่ายทอด ภาพต่อไปนี้แสดงภาพวาดของกราฟที่สอดคล้องกับความสัมพันธ์ทวิภาคที่ไม่เป็นเชิงถ่ายทอด (ด้านซ้าย) และการลดรูปเชิงถ่ายทอด (ด้านขวา)

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

ในทฤษฎีทางคณิตศาสตร์ของความสัมพันธ์ทวิภาคความสัมพันธ์ใดๆRบนเซตXอาจถูกมองว่าเป็นกราฟแบบมีทิศทางที่มีเซตXเป็นเซตจุดยอด และมีส่วนโค้งxyสำหรับทุกคู่ลำดับขององค์ประกอบที่สัมพันธ์กันในRโดยเฉพาะอย่างยิ่ง วิธีนี้ช่วยให้เซตที่มีลำดับบางส่วนสามารถตีความใหม่ได้เป็นกราฟแบบมีทิศทางที่ไม่มีวงจร ซึ่งมีส่วนโค้งxyในกราฟเมื่อใดก็ตามที่มีความสัมพันธ์ลำดับx  <  yระหว่างคู่ขององค์ประกอบที่มีลำดับบางส่วน เมื่อใช้การดำเนินการลดรูปเชิงถ่ายทอดกับกราฟแบบมีทิศทางที่ไม่มีวงจรซึ่งสร้างขึ้นด้วยวิธีนี้ มันจะสร้างความสัมพันธ์แบบครอบคลุมของลำดับบางส่วน ซึ่งมักจะแสดงออกมาในรูปแบบภาพโดยใช้แผนภาพ Hasse

การลดแบบถ่ายทอดได้ถูกนำมาใช้กับเครือข่ายที่สามารถแสดงเป็นกราฟแบบไม่มีวงจรทิศทาง (เช่นกราฟการอ้างอิงหรือเครือข่ายการอ้างอิง ) เพื่อเปิดเผยความแตกต่างเชิงโครงสร้างระหว่างเครือข่าย^{[ 2 ]}

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

อย่างไรก็ตาม การระบุลักษณะกราฟขั้นต่ำที่มีความสัมพันธ์การเข้าถึงแบบเดียวกันกับกราฟG ที่กำหนดนั้นเป็นเรื่องง่าย ^{[ 3 ]}ถ้าGเป็นกราฟทิศทางใดๆ และH เป็นกราฟที่มีจำนวนขอบน้อยที่สุดเท่าที่จะเป็นไป ได้ซึ่งมีความสัมพันธ์การเข้าถึงแบบเดียวกันกับGแล้วHประกอบด้วย

• วงจรทิศทางสำหรับแต่ละส่วนประกอบที่เชื่อมต่อกันอย่างแน่นหนาของGซึ่งเชื่อมต่อจุดยอดในส่วนประกอบนี้เข้าด้วยกัน
• สำหรับแต่ละขอบXY ของการลดรูปเชิงถ่ายทอดของการควบแน่นของGโดยที่XและYเป็นส่วนประกอบที่เชื่อมต่อกันอย่างแน่นหนา 2 ส่วนของG ที่เชื่อมต่อกันด้วยขอบในการควบแน่นxคือจุดยอดใดๆ ในส่วนประกอบXและyคือจุดยอดใดๆ ในส่วนประกอบYการควบแน่นของGเป็นกราฟแบบมีทิศทางและไม่มีวงจร ซึ่งมีจุดยอดสำหรับทุกส่วนประกอบที่เชื่อมต่อกันอย่างแน่นหนาของGและมีขอบสำหรับทุก 2 ส่วนประกอบที่เชื่อมต่อกันด้วยขอบในGโดยเฉพาะอย่างยิ่ง เนื่องจากไม่มีวงจร การลดรูปเชิงถ่ายทอดจึงสามารถกำหนดได้ดังในส่วนก่อนหน้า

จำนวนขอบทั้งหมดในการลดรูปเชิงถ่ายทอดประเภทนี้จะเท่ากับจำนวนขอบในการลดรูปเชิงถ่ายทอดของการควบแน่น บวกกับจำนวนจุดยอดในส่วนประกอบที่เชื่อมต่อกันอย่างแน่นหนาที่ไม่ใช่จุดยอดว่าง (ส่วนประกอบที่มีจุดยอดมากกว่าหนึ่งจุด)

ขอบของการลดแบบทรานซิทีฟที่สอดคล้องกับขอบการควบแน่นสามารถเลือกให้เป็นกราฟย่อยของกราฟG ที่กำหนดได้เสมอ อย่างไรก็ตาม วงจรภายในส่วนประกอบที่เชื่อมต่อกันอย่างแน่นหนาแต่ละส่วนสามารถเลือกให้เป็นกราฟย่อยของG ได้ก็ต่อ เมื่อส่วนประกอบนั้นมีวงจรแฮมิลโทเนียนซึ่งไม่เป็นจริงเสมอไปและตรวจสอบได้ยาก เนื่องจากความยากลำบากนี้การค้นหากราฟย่อยที่เล็กที่สุดของกราฟG ที่กำหนด ด้วยการเข้าถึงได้เดียวกัน (กราฟเทียบเท่าขั้นต่ำ) จึง เป็น ปัญหา NP-hard ^{[ 3 ]}

Aho และคณะได้ยกตัวอย่างค้านต่อไปนี้เพื่อแสดงให้เห็นว่า ในกราฟอนันต์เป็นเรื่องยากที่จะกำหนดเงื่อนไขความน้อยที่สุดที่ขยายการลดรูปเชิงถ่ายทอดจากกราฟจำกัดได้อย่างชัดเจน เป็นเรื่องยากแม้กระทั่งในกรณีที่กราฟไม่มีวัฏจักร โดยเลือกนิยามของความน้อยที่สุดเป็น "ไม่มีเซตย่อยแท้ใดที่เป็นการลดรูปเชิงถ่ายทอดด้วย" พวกเขาได้ยกตัวอย่างค้านต่อไปนี้

สร้างกราฟที่มีจุดยอดสำหรับจำนวนจริง แต่ละจำนวน โดยมีขอบเมื่อใดก็ตามที่เป็นจำนวนจริง จากนั้นกราฟนี้จะเป็นอนันต์ ไม่มีวัฏจักร และปิดแบบส่งผ่าน อย่างไรก็ตาม ในกราฟย่อยใดๆ ที่มีการปิดแบบส่งผ่านเหมือนกัน ขอบที่เหลือแต่ละขอบสามารถถูกลบออกได้โดยไม่ทำให้การปิดแบบส่งผ่านเปลี่ยนแปลง เนื่องจากยังคงต้องมีเส้นทางจากไปยังผ่านจุดยอดใดๆ ระหว่างกัน ดังนั้น ในบรรดากราฟย่อยที่มีการปิดแบบส่งผ่านเหมือนกัน จะไม่มีกราฟย่อยใดเป็นกราฟย่อยที่เล็กที่สุด (ตามคำจำกัดความของเซตย่อยที่เหมาะสม): ไม่มีการลดแบบส่งผ่าน^{[ 3 ]}${\displaystyle x\to y}$${\displaystyle x<y}$${\displaystyle x\to y}$${\displaystyle x}$${\displaystyle y}$

ดังที่ Aho และคณะแสดงให้เห็น^{[ 3 ]}เมื่อความซับซ้อนของเวลาของอัลกอริทึมกราฟถูกวัดเป็นฟังก์ชันของจำนวน จุดยอด nในกราฟเท่านั้น และไม่ใช่ฟังก์ชันของจำนวนขอบ การปิดแบบส่งผ่านและการลดแบบส่งผ่านของกราฟแบบไม่มีวงจรทิศทางมีความซับซ้อนเท่ากัน ก่อนหน้านี้ได้แสดงให้เห็นแล้วว่าการปิดแบบส่งผ่านและการคูณเมทริกซ์บูลีนขนาดn  ×  nมีความซับซ้อนเท่ากัน^{[ 4 ]}ดังนั้นผลลัพธ์นี้จึงทำให้การลดแบบส่งผ่านอยู่ในกลุ่มเดียวกันอัลกอริทึมที่แม่นยำที่สุดสำหรับการคูณเมทริกซ์ณ ปี 2023 ใช้เวลา O( n ^2.371552 ) ^{[ 5 ]}และนี่ให้ขอบเขตเวลากรณีเลวร้ายที่สุดที่เร็วที่สุดที่ทราบสำหรับการลดแบบส่งผ่านในกราฟหนาแน่น โดยการนำไปใช้กับเมทริกซ์เหนือจำนวนเต็มและพิจารณารายการที่ไม่เป็นศูนย์ในผลลัพธ์

เพื่อพิสูจน์ว่าการลดแบบทรานซิทีฟนั้นง่ายเหมือนกับการปิดแบบทรานซิทีฟ Aho และคณะอาศัยความเท่าเทียมกันที่ทราบอยู่แล้วกับการคูณเมทริกซ์บูลีน พวกเขากำหนดให้Aเป็นเมทริกซ์ประชิดของกราฟแบบไม่มีวงจรทิศทางที่กำหนด และBเป็นเมทริกซ์ประชิดของการปิดแบบทรานซิทีฟ (คำนวณโดยใช้อัลกอริทึมการปิดแบบทรานซิทีฟมาตรฐานใดๆ) จากนั้นขอบuvเป็นส่วนหนึ่งของการลดแบบทรานซิทีฟก็ต่อเมื่อมีรายการที่ไม่เป็นศูนย์ในแถวuและคอลัมน์vของเมทริกซ์Aและมีรายการที่เป็นศูนย์ในตำแหน่งเดียวกันของผลคูณเมท ริกซ์ ABในการสร้างนี้ องค์ประกอบที่ไม่เป็นศูนย์ของเมทริกซ์ABแสดงถึงคู่ของจุดยอดที่เชื่อมต่อกันด้วยเส้นทางที่มีความยาวสองหรือมากกว่า^{[ 3 ]}

เพื่อพิสูจน์ว่าการลดแบบทรานซิทีฟนั้นยากพอๆ กับการปิดแบบทรานซิทีฟ Aho และคณะได้สร้างกราฟ H อีกกราฟหนึ่งจากกราฟแบบไม่มีวงจรทิศทาง G ที่กำหนดให้โดยที่แต่ละจุดยอดของGจะถูกแทนที่ด้วยเส้นทางที่มีสามจุดยอด และแต่ละขอบของGจะสอดคล้องกับขอบในHที่เชื่อมต่อจุดยอดตรงกลางที่สอดคล้องกันของเส้นทางเหล่านี้ นอกจากนี้ ในกราฟH Aho และคณะได้เพิ่มขอบจากจุดเริ่มต้นของเส้นทางทุกเส้นไปยังจุดสิ้นสุดของเส้นทางทุกเส้น ในการลดแบบทรานซิทีฟของHจะมีขอบจากจุดเริ่มต้นของเส้นทางสำหรับuไปยังจุดสิ้นสุดของเส้นทางสำหรับvก็ต่อเมื่อขอบuvไม่ได้อยู่ในการปิดแบบทรานซิทีฟของGดังนั้น หากการลดแบบทรานซิทีฟของHสามารถคำนวณได้อย่างมีประสิทธิภาพ การปิดแบบทรานซิทีฟของGก็สามารถอ่านได้โดยตรงจากมัน^{[ 3 ]}

เมื่อวัดทั้งในแง่ของจำนวน จุดยอด nและจำนวน ขอบ mในกราฟแบบมีทิศทางและไม่มีวงจร การลดรูปเชิงส่งผ่านก็สามารถหาได้ในเวลา O( nm ) ซึ่งเป็นขอบเขตที่อาจเร็วกว่าวิธีการคูณเมทริกซ์สำหรับกราฟแบบเบาบางในการทำเช่นนั้น ให้ใช้อัลกอริธึมหาเส้นทางที่ยาวที่สุดแบบเชิง เส้นในกราฟแบบมีทิศทางและไม่มีวงจรที่กำหนด สำหรับแต่ละตัวเลือกที่เป็นไปได้ของจุดเริ่มต้น จากเส้นทางที่ยาวที่สุดที่คำนวณได้ ให้เก็บเฉพาะเส้นทางที่มีความยาวหนึ่ง (ขอบเดียว) กล่าวคือ เก็บขอบ ( u , v ) ที่ไม่มีเส้นทางอื่นจากuไปยังv ขอบเขตเวลา O( nm ) นี้ตรงกับความซับซ้อนของการสร้างการปิดเชิงส่งผ่านโดยใช้การค้นหาแบบเจาะลึกหรือการค้นหาแบบกว้างเพื่อค้นหาจุดยอดที่เข้าถึงได้จากทุกตัวเลือกของจุดเริ่มต้น ดังนั้นด้วยสมมติฐานเหล่านี้ การปิดเชิงส่งผ่านและการลดรูปเชิงส่งผ่านจึงสามารถหาได้ในเวลาเดียวกัน

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

• สำหรับแต่ละจุดยอดvโดยเรียงลำดับย้อนกลับตามลำดับโทโพโลยีของกราฟอินพุต:
  • กำหนดเซตของจุดยอดที่สามารถเข้าถึงได้จากvโดยเริ่มต้นเป็นเซตที่มีจุดยอดเดียวคือ { v }
  • สำหรับแต่ละขอบvwตามลำดับโทโพโลยีโดยwให้ตรวจสอบว่าwอยู่ในเซตที่เข้าถึงได้ของv หรือ ไม่ และถ้าไม่:
    • ขอบเอาต์พุตvwเป็นส่วนหนึ่งของการลดรูปเชิงถ่ายทอด
    • แทนที่เซตของจุดยอดที่สามารถเข้าถึงได้จากv ด้วยการรวมกัน ของเซตนั้นกับเซตที่สามารถเข้าถึงได้จากw

ลำดับของขอบในลูปภายในสามารถหาได้โดยใช้การเรียงลำดับแบบนับ สองรอบ หรืออัลกอริทึมการเรียงลำดับแบบเสถียร อื่น ๆ เพื่อเรียงลำดับขอบ โดยเริ่มจากการกำหนดหมายเลขโทโพโลยีของจุดปลาย และลำดับที่สองตามจุดเริ่มต้น หากเซตถูกแทนด้วยอาร์เรย์บิตการดำเนินการรวมเซตแต่ละครั้งสามารถทำได้ในเวลาO ( n ) หรือเร็วกว่านั้นโดยใช้การดำเนินการแบบบิตจำนวนของการดำเนินการเซตเหล่านี้เป็นสัดส่วนกับจำนวนขอบเอาต์พุต ซึ่งนำไปสู่ขอบเขตเวลาโดยรวมของO ( nr ) เซตที่เข้าถึงได้ซึ่งได้มาในระหว่างอัลกอริทึมจะอธิบายการปิดแบบส่งผ่านของอินพุต^{[ 6 ]}

หากกราฟถูกระบุพร้อมกับการแบ่งจุดยอดของกราฟออกเป็นkโซ่ (เซตย่อยที่เข้าถึงได้เป็นคู่ๆ) เวลาดังกล่าวสามารถลดลงได้อีกเป็นO ( kr ) โดยการแสดงเซตที่เข้าถึงได้แต่ละเซตอย่างกระชับในรูปของการรวมกันของส่วนท้ายของโซ่^{[ 7 ]}

• ไวส์สไตน์, เอริค ดับเบิลยู. , "การลดรูปเชิงถ่ายทอด" , MathWorld