ส่วนประกอบที่เชื่อมกันแบบเข้ม
![]() | ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e1/Scc-1.svg/220px-Scc-1.svg.png)
ส่วนประกอบที่เชื่อมกันแบบเข้ม (อังกฤษ: Strongly Connected Component : SCC) คือ กราฟที่เชื่อมกันแบบเข้ม (Strongly Connected Graph) ซึ่งเป็นกราฟย่อยที่ใหญ่ที่สุดในกราฟใหญ่ หรือ กราฟย่อยใหญ่ที่สุดที่เป็นการเชื่อมกันแบบเข้ม
กราฟที่เชื่อมกันแบบเข้ม
[แก้]กราฟที่เชื่อมกันแบบเข้ม (อังกฤษ: 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 จุดและนำมาเชื่อมกันเป็นกราฟใหญ่เหมือนตอนแรก
- เมื่อประกอบกันแล้วตรวจสอบสีส่วนที่เชื่อมกันระหว่างสองส่วนว่ามีสีเดียวกันอยู่ติดกันหรือไม่ ถ้ามีให้ทำการสับเปลี่ยนสีไปเรื่อยๆ หากสับเปลี่ยนไม่ได้แล้วก็ให้เพิ่มสีใหม่เข้าไปในกราฟจะได้กราฟที่มีการให้สีที่สมบูรณ์เรียบร้อยแล้วโดยใช้เวลาที่เร็วกว่าการทำด้วยวิธีเอ็นพีบริบูรณ์แบบธรรมดา
ข้อดี
[แก้]- เป็นการแก้ปัญหาที่เร็วมากเพราะเหมือนเป็นการทำที่ขนานกัน คือ ส่วนประกอบที่เชื่อมกันแบบเข้มแต่ละส่วนมีการถูกให้สีไปพร้อมๆกันก่อนที่จะนำมารวมกัน
- เป็นการลดความซับซ้อนในการแก้ปัญหาอย่างมาก เพราะมีการทำที่เป็นขั้นตอนคือ แบ่งเป็นส่วนประกอบที่เชื่อมกันแบบเข้มก่อนแล้วจึงนำมาเชื่อมกัน ทำให้ได้กราฟที่สมบูรณ์
อ้างอิง
[แก้]- Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E. (1979), "A linear-time algorithm for testing the truth of certain quantified boolean formulas", Information Processing Letters, 8 (3): 121–123, doi:10.1016/0020-0190(79)90002-4.
- 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.