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

ส่วนประกอบที่อ่อนแอได้รับการกำหนดไว้ในบทความปี 1972 โดยRonald Graham , Donald Knuthและ (หลังเสียชีวิต) Theodore Motzkinโดยเปรียบเทียบกับส่วนประกอบที่เชื่อมต่ออย่างแน่นหนาของกราฟแบบมีทิศทาง ซึ่งก่อให้เกิดการแบ่งย่อยจุดยอดของกราฟที่ละเอียดที่สุดเท่าที่จะเป็นไปได้เป็นเซตย่อยที่เรียงลำดับบางส่วนตามการเข้าถึงได้ ในทางกลับกัน พวกเขากำหนดส่วนประกอบที่อ่อนแอให้เป็นการแบ่งย่อยจุดยอดที่ละเอียดที่สุดเป็นเซตย่อยที่เรียงลำดับทั้งหมดตามการเข้าถึงได้^{[ 1 ] [ 2 ]}

กล่าวโดยละเอียดKnuth (2022)นิยามส่วนประกอบที่อ่อนแอผ่านการรวมกันของความสัมพันธ์สมมาตร สี่ประการ บนจุดยอดของกราฟทิศทางใดๆ ซึ่งในที่นี้แสดงด้วย , , , และ:${\displaystyle \Leftrightarrow }$${\displaystyle \parallel }$${\displaystyle \approx }$${\displaystyle \asymp }$

• สำหรับจุดยอดสองจุดใดๆและในกราฟถ้าและเฉพาะเมื่อจุดยอดแต่ละจุดสามารถเข้าถึงได้จากอีกจุดยอดหนึ่ง จะมีเส้นทางในกราฟจากไปยังและจากไปยังความ สัมพันธ์ นี้เป็นความสัมพันธ์สมมูลและชั้นสมมูล ของความสัมพันธ์นี้ ใช้ในการกำหนดส่วนประกอบที่เชื่อมต่อกันอย่างแน่นแฟ้นของกราฟ${\displaystyle u}$${\displaystyle v}$${\displaystyle u\ลูกศรซ้าย v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle v}$${\displaystyle u}$${\displaystyle \Leftrightarrow }$
• สำหรับจุดยอดสองจุดใดๆและในกราฟก็ต่อเมื่อไม่สามารถเข้าถึงจุดยอดทั้งสองได้: จะไม่มีเส้นทางในกราฟในทิศทางใดๆระหว่างและ${\displaystyle u}$${\displaystyle v}$${\displaystyle u\parallel v}$${\displaystyle u}$${\displaystyle v}$
• สำหรับจุดยอดสองจุดใดๆของกราฟก็ต่อเมื่อ หรือนั่นคืออาจมีการเชื่อมต่อแบบสองทางระหว่างจุดยอดเหล่านี้ หรืออาจไม่สามารถเข้าถึงกันได้ แต่จะไม่มีการเชื่อมต่อแบบทางเดียว${\displaystyle u}$${\displaystyle v}$${\displaystyle u\approx v}$${\displaystyle u\ลูกศรซ้าย v}$${\displaystyle u\parallel v}$
• ความสัมพันธ์นี้ถูกนิยามว่าเป็นการปิดแบบถ่ายทอดของนั่นคือเมื่อมีลำดับของจุดยอดที่เริ่มต้นด้วยและสิ้นสุดด้วยโดยที่แต่ละคู่ที่อยู่ติดกันในลำดับนั้นมีความสัมพันธ์กันโดย${\displaystyle \asymp }$${\displaystyle \approx }$${\displaystyle u\asymp v}$${\displaystyle u\approx \cdots \approx v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle \approx }$

จากนั้นจะเป็นความสัมพันธ์สมมูล: จุดยอดทุกจุดมีความสัมพันธ์กับตัวเองโดย(เนื่องจากสามารถเข้าถึงตัวเองได้ทั้งสองทิศทางโดยเส้นทางที่มีความยาวเป็นศูนย์) จุดยอดสองจุดใดๆ ที่มีความสัมพันธ์กันโดยสามารถสลับกันได้โดยไม่เปลี่ยนแปลงความสัมพันธ์นี้ (เนื่องจากสร้างขึ้นจากความสัมพันธ์สมมาตรและ)และเป็นความสัมพันธ์แบบถ่ายทอด (เนื่องจากเป็นการปิดแบบถ่ายทอด) เช่นเดียวกับความสัมพันธ์สมมูลใดๆ สามารถใช้เพื่อแบ่งจุดยอดของกราฟออกเป็นชั้นสมมูล ซึ่งเป็นเซตย่อยของจุดยอดที่จุดยอดสองจุดมีความสัมพันธ์กันโดยก็ต่อเมื่อจุดยอดทั้งสองอยู่ในชั้นสมมูลเดียวกัน ชั้นสมมูลเหล่านี้คือส่วนประกอบอ่อนของกราฟ ที่กำหนด ^{[ 2 ]}${\displaystyle \asymp }$${\displaystyle \asymp }$${\displaystyle \asymp }$${\displaystyle \asymp }$${\displaystyle \Leftrightarrow }$${\displaystyle \parallel }$${\displaystyle \asymp }$${\displaystyle \asymp }$

นิยามดั้งเดิมโดย Graham, Knuth และ Motzkin นั้นเทียบเท่ากัน แต่ถูกกำหนดสูตรแตกต่างกันเล็กน้อย เมื่อกำหนดกราฟ${\displaystyle G}$ ทิศทาง พวกเขาสร้างกราฟอีกกราฟหนึ่งก่อนเป็นกราฟส่วนเติมเต็มของการปิดแบบทรานซิทีฟของตามที่Tarjan (1974)อธิบายไว้ ขอบในแสดงถึงไม่ใช่เส้นทาง คู่ของจุดยอดที่ไม่ได้เชื่อมต่อ กันด้วยเส้นทางใน^{[ 3 ]}จากนั้น จุดยอดสองจุดจะอยู่ในส่วนประกอบอ่อนเดียวกันเมื่ออยู่ในส่วนประกอบที่เชื่อมต่อกันอย่างแน่นหนาเดียวกันของหรือของ[ ^{1 ] [ 3 ] ดัง}ที่ Graham, Knuth และ Motzkin แสดงให้เห็น เงื่อนไขนี้กำหนดความสัมพันธ์ สมมูล ^{[ 1 ]}ซึ่งเป็นความสัมพันธ์เดียวกันกับที่กำหนดไว้ข้าง^ต้นเป็น[ ^{4 ]}${\displaystyle {\hat {G}}}$${\displaystyle G}$${\displaystyle {\hat {G}}}$${\displaystyle G}$${\displaystyle G}$${\displaystyle {\hat {G}}}$${\displaystyle \asymp }$

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

ถ้าและเป็นส่วนประกอบที่อ่อนแอสองส่วนของกราฟทิศทาง แล้วจุดยอดทั้งหมดในสามารถเข้าถึงจุดยอดทั้งหมดใน ได้โดยใช้เส้นทางในกราฟ หรือจุดยอดทั้งหมดในสามารถเข้าถึงจุดยอดทั้งหมดใน ได้อย่างไรก็ตามไม่สามารถมีความสัมพันธ์ในการเข้าถึงได้ทั้งสองทิศทางระหว่างส่วนประกอบทั้งสองนี้ ดังนั้น เราสามารถกำหนดลำดับบนส่วนประกอบที่อ่อนแอได้ โดยที่จุดยอดทั้งหมดในสามารถเข้าถึงจุดยอดทั้งหมดใน ได้ตามคำนิยามนี่คือความสัมพันธ์แบบไม่สมมาตร (องค์ประกอบสองตัวสามารถมีความสัมพันธ์กันได้เพียงทิศทางเดียวเท่านั้น ไม่ใช่อีกทิศทางหนึ่ง) และสืบทอดคุณสมบัติของการเป็นความสัมพันธ์แบบถ่ายทอดจากคุณสมบัติการถ่ายทอดของการเข้าถึงได้ ดังนั้น มันจึงกำหนดลำดับทั้งหมดบนส่วนประกอบที่อ่อนแอ เป็นการแบ่งจุดยอดที่ละเอียดที่สุดที่เป็นไปได้ออกเป็นเซตของจุดยอดที่มีลำดับทั้งหมดซึ่งสอดคล้องกับการเข้าถึงได้^{[ 1 ]}${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle X<Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X\nless X}$

ลำดับนี้บนส่วนประกอบที่อ่อนแอสามารถตีความได้อีกอย่างว่าเป็นลำดับที่อ่อนแอของจุดยอดเอง โดยมีคุณสมบัติว่าเมื่ออยู่ในลำดับที่อ่อนแอ จะต้องมีเส้นทางจากไปยังแต่ไม่มีเส้นทางจากไปยังอย่างไรก็ตามนี่ไม่ใช่ลักษณะเฉพาะที่สมบูรณ์ของลำดับที่อ่อนแอนี้ เนื่องจากจุดยอดสองจุดและอาจมีลำดับการเข้าถึงแบบเดียวกันนี้ในขณะที่อยู่ในส่วนประกอบที่อ่อนแอเดียวกัน^{[ 2 ]}${\displaystyle u<v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle v}$${\displaystyle u}$${\displaystyle u}$${\displaystyle v}$

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

Pacault (1974)ได้อธิบายอัลกอริธึมสำหรับการคำนวณส่วนประกอบที่อ่อนแอของกราฟทิศทางที่กำหนดในเวลาเชิงเส้นและต่อมาTarjan (1974)และKnuth (2022)ได้ ทำให้ง่ายขึ้น ^{[ 2 ] [ 3 ] [ 5 ]}ดังที่ Tarjan สังเกตอัลกอริธึมส่วนประกอบที่เชื่อมต่ออย่างแน่นหนาของ Tarjanซึ่งอิงตามการค้นหาแบบเจาะลึกจะส่งออกส่วนประกอบที่เชื่อมต่ออย่างแน่นหนาในลำดับที่เรียงลำดับตามโทโพโลยี (แบบย้อนกลับ) อัลกอริธึมสำหรับส่วนประกอบที่อ่อนแอจะสร้างส่วนประกอบที่เชื่อมต่ออย่างแน่นหนาในลำดับนี้ และรักษาการแบ่งส่วนของส่วนประกอบที่สร้างขึ้นจนถึงขณะนี้เป็นส่วนประกอบที่อ่อนแอของ กราฟ ย่อยที่เหนี่ยวนำหลังจากสร้างส่วนประกอบทั้งหมดแล้ว การแบ่งส่วนนี้จะอธิบายส่วนประกอบที่อ่อนแอของกราฟ ทั้งหมด ^{[ 2 ] [ 3 ]}

เป็นการสะดวกที่จะรักษาการแบ่งส่วนปัจจุบันเป็นส่วนประกอบที่อ่อนแอในสแต็กโดยแต่ละส่วนประกอบที่อ่อนแอจะรักษารายการแหล่งที่มา เพิ่มเติม ซึ่งเป็นส่วนประกอบที่เชื่อมต่ออย่างแน่นหนาที่ไม่มีขอบขาเข้าจากส่วนประกอบที่เชื่อมต่ออย่างแน่นหนาอื่น ๆ ในส่วนประกอบที่อ่อนแอเดียวกัน โดยให้แหล่งที่มาที่สร้างขึ้นล่าสุดอยู่ก่อน ส่วนประกอบที่เชื่อมต่ออย่างแน่นหนาที่สร้างขึ้นใหม่แต่ละส่วนอาจสร้างส่วนประกอบที่อ่อนแอใหม่ได้ด้วยตัวเอง หรืออาจรวมเข้ากับส่วนประกอบที่อ่อนแอที่สร้างขึ้นก่อนหน้านี้บางส่วนที่อยู่ใกล้ด้านบนของสแต็ก ซึ่งเป็นส่วนประกอบที่ไม่สามารถเข้าถึงแหล่งที่มาทั้งหมดได้^{[ 2 ] [ 3 ]}

ดังนั้นอัลกอริทึมจึงดำเนินการตามขั้นตอนต่อไปนี้: ^{[ 2 ] [ 3 ]}

• เริ่มต้นสร้างสแต็กว่างเปล่าของส่วนประกอบที่อ่อนแอ โดยแต่ละส่วนประกอบจะเชื่อมโยงกับรายการของส่วนประกอบต้นทาง
• ใช้ขั้นตอนวิธีส่วนประกอบที่เชื่อมต่ออย่างแน่นหนาของ Tarjan เพื่อสร้างส่วนประกอบที่เชื่อมต่ออย่างแน่นหนาของกราฟที่กำหนด โดยเรียงลำดับย้อนกลับจากลำดับเชิงโทโพโลยี เมื่อสร้างส่วนประกอบที่เชื่อมต่ออย่างแน่นหนาแต่ละส่วนแล้ว ให้ดำเนินการตามขั้นตอนต่อไปนี้: ${\displaystyle S}$
  • ในขณะที่สแต็กไม่ว่างเปล่าและไม่มีขอบเชื่อมไปยังส่วนประกอบที่อ่อนแอที่สุดด้านบนสุดของสแต็ก ให้ดึงส่วนประกอบนั้นออกจากสแต็ก${\displaystyle S}$
  • หากสแต็กยังคงไม่ว่างเปล่า และแหล่งที่มาบางส่วนของส่วนประกอบที่อ่อนแอที่สุดด้านบนยังไม่ถูกกระทบโดยขอบจากให้${\displaystyle S}$ดึงส่วนประกอบนั้นออกจากสแต็กอีกครั้ง
  • สร้างคอมponent อ่อนตัวใหม่ โดย${\displaystyle W}$มีแหล่งที่มาทั้งหมดที่ยังไม่ถูกเรียกใช้จากคอมponent บนสุดที่ถูกดึงออกไปเป็นแหล่งที่มาเหล่านั้น แล้วผลักคอมponent นั้นลงบนสแต็ก${\displaystyle S}$${\displaystyle W}$

การทดสอบแต่ละครั้งว่ามีขอบใดกระทบกับส่วนประกอบที่อ่อนแอหรือไม่ สามารถดำเนินการได้ในเวลาคงที่เมื่อเราพบขอบจากส่วนประกอบที่เชื่อมต่ออย่างแน่นหนาที่สร้างขึ้นก่อนหน้านี้ล่าสุด โดยการเปรียบเทียบส่วนประกอบเป้าหมายของขอบนั้นกับแหล่งที่มาแรกของส่วนประกอบลำดับที่สองจากบนสุดในสแต็ก ${\displaystyle S}$${\displaystyle S}$

• Knuth, Donald E. (5 ธันวาคม 2024), ส่วนประกอบที่แข็งแกร่งและส่วนประกอบที่อ่อนแอ , การบรรยายคริสต์มาสประจำปี (วิดีโอ), มหาวิทยาลัยสแตนฟอร์ด