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

จากวิกิพีเดีย สารานุกรมเสรี
กราฟแสดงส่วนประกอบที่เชื่อมกันแบบเข้ม โดยในกราฟมีทั้งหมด 3 ส่วน

ส่วนประกอบที่เชื่อมกันแบบเข้ม (อังกฤษ: 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) แต่ขั้นตอนวิธีของทาร์จัน และขั้นตอนวิธีของกาโบว์ นั้นมักจะถูกนำมาใช้ในทางปฏิบัติมากกว่าเพราะว่าให้ประสิทธิภาพที่ดีกว่า เนื่องจากมีการเดินทางเข้าไปในกราฟเพียงแค่รอบเดียวเท่านั้น ต่างจากขั้นตอนวิธีของโกสรชุ ซึ่งต้องเดินทางเข้าไปในกราฟถึงสองครั้ง

ประสิทธิภาพการทำงาน[แก้]

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

- ขั้นตอนวิธีของโกสรชุ จะมีประสิทธิภาพเป็น  \Theta (V+E) เมื่อ V แทนจำนวนจุดยอด และ E แทนจำนวนเส้นเชื่อม

- ขั้นตอนวิธีของทาร์จัน จะมีประสิทธิภาพเป็น  O (V+E)  เมื่อ  V แทนจำนวนจุดยอด และ E แทนจำนวนเส้นเชื่อม

การนำไปใช้งาน[แก้]

การเชื่อมโยงกันของเว็บไซต์[แก้]

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

ช่วยแก้ปัญหาเอ็นพีบริบูรณ์[แก้]

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

วิธีการทำ[แก้]

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

ข้อดี[แก้]

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

อ้างอิง[แก้]

แหล่งข้อมูลอื่น[แก้]