Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
ส่วนประกอบที่เชื่อมกันแบบเข้ม (อังกฤษ: 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.; (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. . 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 2011-10-06 ที่ เวย์แบ็กแมชชีน
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
lingkkhamphasa inbthkhwamni miiwihphuxanaelaphurwmaekikhbthkhwamsuksaephimetimodysadwk enuxngcakwikiphiediyphasaithyyngimmibthkhwamdngklaw krann khwrribsrangepnbthkhwamodyerwthisud swnprakxbthiechuxmknaebbekhm xngkvs Strongly Connected Component SCC khux krafthiechuxmknaebbekhm Strongly Connected Graph sungepnkrafyxythiihythisudinkrafihy hrux krafyxyihythisudthiepnkarechuxmknaebbekhmkrafaesdngswnprakxbthiechuxmknaebbekhm odyinkrafmithnghmd 3 swn krafthiechuxmknaebbekhm krafthiechuxmknaebbekhm xngkvs Strongly Connected Graph khux krafrabuthisthang directed graph thimi withi rahwangthukkhupm thngipaelaklb hrux withi cakaetlacudinkraf ipyngthukcudxuninkraf odyechphaainthinihmaythung thami withicak a ip b aelwkcatxngmiwithicak b klbma a dwyechnknkhntxnwithiinkarhakhntxnwithiinkarha swnprakxbthiechuxmknaebbekhminkrafthiechuxmknaebbekhmnnmihlaywithi thimiprasiththiphaphdithiniymich idaek khntxnwithikhxngoksrchu Kosaraju s algorithm khntxnwithikhxngtharcn Tarjan s algorithm aelakhntxnwithikhxngkaobw Gabow s algorithm aetkhntxnwithikhxngtharcn aelakhntxnwithikhxngkaobw nnmkcathuknamaichinthangptibtimakkwaephraawaihprasiththiphaphthidikwa enuxngcakmikaredinthangekhaipinkrafephiyngaekhrxbediywethann tangcakkhntxnwithikhxngoksrchu sungtxngedinthangekhaipinkrafthungsxngkhrngprasiththiphaphkarthanganprasiththiphaphkarthanganinkarhaswnprakxbthiechuxmknaebbekhminkrafthiechuxmknaebbekhmnn cakhunxyukbwacaichkhntxnwithiaebbidinkarhadngni khntxnwithikhxngoksrchu camiprasiththiphaphepn 8 V E displaystyle Theta V E emux V displaystyle V aethncanwncudyxd aela E displaystyle E aethncanwnesnechuxm khntxnwithikhxngtharcn camiprasiththiphaphepn O V E displaystyle O V E emux V displaystyle V aethncanwncudyxd aela E displaystyle E aethncanwnesnechuxmkarnaipichngankarechuxmoyngknkhxngewbist mikarnakhwamruthangdanokhrngsrangkrafipichpraoychninkarkarpramwlphl hruxkarsubkhnkhxmultanginthangxinethxrent Information Retrieval ephuxihkarsubkhnkhxmultangsamarththaidngayyingkhun aelainkarichngan swnprakxbthiechuxmknaebbekhm Strongly Connected Component nicaichinepnlksnakarechuxmoyngknkhxngewbist sungepnklumkhxngewbistthiepnthiniym odyewbistinklumnicamikarechuxmoyngknexngxyangehniywaenn enuxngcakinklumtangkepnthiniyminxinethxrentechnkn twenuxha mkepnenuxhathiphubriophkhkhxmulkhawsarnntxngkar cungepneruxngthrrmdathiewbistehlanicathukewbisthnungxangthung aeladwyprimanphuichthimakcungkhbekhluxnphuichodykarxangipyngewbistxunxikechnkn chwyaekpyhaexnphibriburn nakhwamruinkarhaswnprakxbthiechuxmknaebbekhm ipichinpyhaaebbexnphibriburn ephuxchwyihaekpyhaidngayaelaerwkhun yktwxyangechn pyhakarihsikraf Graph Coloring sunghakkrafmikhnadihy karichexnphibriburninkaraekpyhanncaichewlananmak sungerasamarthich karhaswnprakxbthiechuxmknaebbekhm machwyihaekidngayaelwerwkhunody withikartha nakrafnnmaaebngepn swnprakxbthiechuxmknaebbekhm sungcaidswnprakxbthiechuxmknaebbekhmmahlayswndwykn ihsiinaetlaswnprakxbthiechuxmknaebbekhminkrafihynn odyihaetlacudinkrafthixyutidknimichsiediywkn naswnprakxbthiechuxmknaebbekhmaetlaswninkrafihynnmarwmkn odymxngwaaetlaswnprakxbthiechuxmknaebbekhmnn epn 1 cudaelanamaechuxmknepnkrafihyehmuxntxnaerk emuxprakxbknaelwtrwcsxbsiswnthiechuxmknrahwangsxngswnwamisiediywknxyutidknhruxim thamiihthakarsbepliynsiiperuxy haksbepliynimidaelwkihephimsiihmekhaipinkrafcaidkrafthimikarihsithismburneriybrxyaelwodyichewlathierwkwakarthadwywithiexnphibriburnaebbthrrmdakhxdi epnkaraekpyhathierwmakephraaehmuxnepnkarthathikhnankn khux swnprakxbthiechuxmknaebbekhmaetlaswnmikarthukihsiipphrxmknkxnthicanamarwmkn epnkarldkhwamsbsxninkaraekpyhaxyangmak ephraamikarthathiepnkhntxnkhux aebngepnswnprakxbthiechuxmknaebbekhmkxnaelwcungnamaechuxmkn thaihidkrafthismburnxangxingAspvall Bengt Plass Michael F 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 aehlngkhxmulxunULearn karxxkaebbxlkxrithum smchay prasiththicutrakul Lecture Note 9 Jan 2007 Graph Structure of The Web HITS and PageRank Making Graph Algorithms Fast using Strongly Connected Components 2011 10 06 thi ewyaebkaemchchin