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

ส่วนประกอบที่เชื่อมกันแบบเข้ม () คือ กราฟที่เชื่อมกันแบบเข้ม (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 

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