ส่วนประกอบที่เชื่อมกันแบบเข้ม

ส่วนประกอบที่เชื่อมกันแบบเข้ม () คือ กราฟที่เชื่อมกันแบบเข้ม (Strongly Connected Graph) ซึ่งเป็นกราฟย่อยที่ใหญ่ที่สุดในกราฟใหญ่ หรือ กราฟย่อยใหญ่ที่สุดที่เป็นการเชื่อมกันแบบเข้ม

 กราฟที่เชื่อมกันแบบเข้ม 
กราฟที่เชื่อมกันแบบเข้ม () คือ กราฟระบุทิศทาง (directed graph) ที่มี วิถี ระหว่างทุก ๆ คู่ปม ทั้งไปและกลับ หรือ วิถี จากแต่ละจุดในกราฟ ไปยังทุกจุดอื่น ๆ ในกราฟ โดยเฉพาะในที่นี้หมายถึง ถ้ามี วิถีจาก a ไป b แล้วก็จะต้องมีวิถีจาก b กลับมา a ด้วยเช่นกัน

 ขั้นตอนวิธีในการหา 
ขั้นตอนวิธีในการหา ส่วนประกอบที่เชื่อมกันแบบเข้มในกราฟที่เชื่อมกันแบบเข้มนั้นมีหลายวิธี ที่มีประสิทธิภาพดีที่นิยมใช้ ได้แก่ ขั้นตอนวิธีของโกสรชุ (Kosaraju's algorithm) ขั้นตอนวิธีของทาร์จัน (Tarjan's algorithm) และขั้นตอนวิธีของกาโบว์ (Gabow's algorithm) แต่ขั้นตอนวิธีของทาร์จัน และขั้นตอนวิธีของกาโบว์  นั้นมักจะถูกนำมาใช้ในทางปฏิบัติมากกว่าเพราะว่าให้ประสิทธิภาพที่ดีกว่า เนื่องจากมีการเดินทางเข้าไปในกราฟเพียงแค่รอบเดียวเท่านั้น ต่างจากขั้นตอนวิธีของโกสรชุ ซึ่งต้องเดินทางเข้าไปในกราฟถึงสองครั้ง

 ประสิทธิภาพการทำงาน 
ประสิทธิภาพการทำงานในการหาส่วนประกอบที่เชื่อมกันแบบเข้มในกราฟที่เชื่อมกันแบบเข้มนั้น จะขึ้นอยู่กับว่าจะใช้ขั้นตอนวิธีแบบใดในการหาดังนี้

ขั้นตอนวิธีของโกสรชุ จะมีประสิทธิภาพเป็น  เมื่อ  แทนจำนวนจุดยอด และ  แทนจำนวนเส้นเชื่อม
ขั้นตอนวิธีของทาร์จัน จะมีประสิทธิภาพเป็น  เมื่อ  แทนจำนวนจุดยอด และ  แทนจำนวนเส้นเชื่อม

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

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

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

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

 อ้างอิง 

 .
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.5, pp. 552-557.

 แหล่งข้อมูลอื่น 
ULearn การออกแบบอัลกอริทึม (สมชาย ประสิทธิ์จูตระกูล)
Lecture Note 9 Jan 2007 Graph Structure of The Web, HITS and PageRank
Making Graph Algorithms Fast, using Strongly Connected Components 

หมวดหมู่:ทฤษฎีกราฟ
หมวดหมู่:วิยุตคณิต
หมวดหมู่:ความต่อเนื่องของกราฟ
หมวดหมู่:ขั้นตอนวิธีกราฟ
หมวดหมู่:กราฟระบุทิศทาง