ปัญหาที่ได้รับความสนใจอย่างมากในเรื่องทฤษฎีกราฟ คือ ปัญหาการระบายสีกราฟ (อังกฤษ : Graph coloring problem ) ซึ่งเป็นปัญหาที่เกี่ยวกับการพยายามระบายสีจุดของกราฟ โดยให้จุดที่อยู่ติดกันมีสีต่างกันและใช้สีให้น้อยที่สุด
การระบายสีบนจุดยอดของกราฟโดยจุดยอดที่มีเส้นเชื่อมถึงกันใช้สีไม่ซ้ำกัน ในกรณีกราฟนี้ต้องใช้สีเป็นอย่างน้อย 3 สี
การระบายสีกราฟอาจมีหลายรูปแบบ บางรูปสามารถใช้สีเพียงสองสีก็เพียงพอที่จะให้จุดที่อยู่ติดกันมีสีต่างกัน บางรูปจำเป็นต้องใช้หลายสีถึงจะเพียงพอที่จะให้จุดที่อยู่ติดกันมีสีต่างกัน ดังนั้นจะเรียกจำนวนสีอย่างน้อยที่สุดที่เพียงพอที่จะให้จุดที่อยู่ติดกันมีสีต่างกันว่า จำนวนสีของกราฟ
ประวัติ สาเหตุหนึ่งที่ทำให้ปัญหาเกี่ยวกับการระบายสีจุดของกราฟได้รับความสนใจศึกษาค้นคว้าเป็นอันมา ได้แก่ ความเกี่ยวข้องกันระหว่างปัญหาเช่นนี้กับปัญหาการระบายสีแผนที่ โดยไม่ให้เนื้อที่ซึ่งมีเส้นเขตแดนร่วมกันมีสีเดียวกัน เราอาจพิจารณาให้เห็นความเกี่ยวข้องอันนี้ได้ไม่ยากนัก
ตัวอย่างเช่นในแผนที่ ถ้าแทนจังหวัดต่าง ๆ ด้วยจุด แล้วลากเส้นโยงจุดซึ่งแทนจังหวัดที่มีเส้นเขตแดนร่วมกัน เราก็จะได้กราฟของแผนที่นี้ไปใช้ในการแก้ปัญหาการระบายสีแผนที่ ซึ่งจะเห็นได้ว่าปัญหาการระบายสีแผนที่กับปัญหาการระบายสีจุดของกราฟ เป็นปัญหาเดียวกัน นอกจากนี้การระบายสีแผนที่นั้น หลายต่อหลายคนเชื่อกันว่าสามารถใช้สีเพียงสี่สีก็เพียงพอที่จะระบายแผนที่ใด ๆ ให้เนื้อที่ที่มีเส้นเขตแดนร่วมกันมีสีต่างกันได้เสมอ ไม่ว่าเนื้อที่ต่าง ๆ ในแผนที่นั้นจะเรียงรายกันอยู่อย่างไร ซึ่งนักคณิตศาสตร์ได้พยายามค้นคว้าหาคำตอบว่า เรื่องที่หลายคนเชื่อกันนี้จริงหรือไม่ การขบคิดปัญหานี้นักคณิตศาสตร์ได้ทำกันมาเป็นเวลานานกว่าร้อยปีจึงมีผู้พิสูจน์ได้ว่าความเชื่อดังกล่าวถูกต้อง
บทนิยามที่เกี่ยวข้อง รงคเลข (Chromatic number χ (G) ) คือจำนวนที่บอกว่ากราฟ G นั้นต้องการสีน้อยที่สุดเท่าไหร่เพื่อระบายบนปมทั้งหมดในกราฟรงคพหุนาม (Chromatic polynomial) จำนวนวิธีในการลงสีกราฟ G โดยใช้จำนวนสีไม่มากไปกว่า จำนวนสีที่ให้มาการระบายสีเส้นเชื่อม (Edge coloring) มีความคล้ายคลึงกับการระบายสีปม แต่จะเป็นการระบายสีลงบนเส้นเชื่อมในกราฟแทน ซึ่งมีข้อจำกัดว่าเส้นเชื่อมที่ต่อกับปมเดียวกัน จะต้องมีสีต่างกัน
ขั้นตอนวิธี การตัดสินใจ (Decision) Input : กราฟ G ซึ่งมีปมเป็นจำนวน v ปม, จำนวนสีเป็นจำนวนเต็ม k สีOutput : ค่าความจริงว่ากราฟ G ลงสีได้ด้วยจำนวนสีน้อยกว่าหรือเท่ากับ k สีหรือไม่เวลาในการทำงาน : O (2n n)ความซับซ้อน : เอ็นพีบริบูรณ์การหาค่าเหมาะสมที่สุด (Optimization) Input : กราฟ G ซึ่งมีปมเป็นจำนวน v ปมOutput : รงคเลขของกราฟ Gเวลาในการทำงาน : O (n (log n) −3 (log log n) 2 )ความซับซ้อน : เอ็นพียากการนับ (Counting) Input : กราฟ G ซึ่งมีปมเป็นจำนวน v ปม, จำนวนสีเป็นจำนวนเต็ม k สีOutput : รงคพหุนามของกราฟ Gเวลาในการทำงาน : O (2n n)ความซับซ้อน : ชาร์ปพีบริบูรณ์
การประยุกต์ใช้ ปัญหาการระบายสีกราฟสามารถนำไปใช้แก้ปัญหาต่าง ๆ ในชีวิตประจำวันได้อย่างมากมาย เช่น
ปัญหาการกำหนดตารางเวลา (Scheduling problem) ปัญหานี้คือการนำงานหลาย ๆ งานมาจัดเรียงใส่ในช่วงเวลาที่ว่างอยู่ โดยงานต่าง ๆ จะต้องการวัตถุดิบเฉพาะงานและงานที่ต้องการวัตถุดิบเดียวกันจะไม่สามารถกระทำพร้อมกันได้ในเวลาใดเวลาหนึ่ง มิฉะนั้นจะเกิดความซ้ำซ้อน จึงต้องอาศัยตารางเวลา เพื่อช่วยในการกำหนดลำดับการทำงานก่อนหลังของงานเหล่านั้น
Input : เซตของงานที่ต้องลงในตารางOutput : เวลาที่น้อยที่สุดที่ใช้ในการทำงานเหล่านั้นจนเสร็จ โดยไม่เกิดความซ้ำซ้อนการแก้ปัญหานี้ด้วยการระบายสีกราฟทำได้โดยการแทนงานด้วยปมของกราฟ และลากเส้นเชื่อมงานที่ต้องใช้วัตถุดิบเดียวกันไว้ด้วยกัน จากนั้นทำการระบายสีกราฟ ผลที่ได้ก็คือจำนวนสีที่น้อยสุดที่ต้องใช้ ซึ่งก็คือระยะเวลาที่น้อยที่สุดที่สามารถทำงานทั้งหมดได้นั่นเอง ปัญหาเกม Sudoku Input : ตารางโจทย์เกม SudokuOutput : คำตอบของโจทย์ข้อนั้น ๆการแก้ปัญหา Sudoku ด้วยการระบายสีกราฟทำได้โดยการแทนช่องในตารางด้วยปมของกราฟ แล้วลากเส้นเชื่อมช่องในตารางที่ห้ามมีเลขซ้ำกันตามกฎของ Sudoku ไว้ด้วยกัน จากนั้นตรวจสอบว่าจำนวนสีที่ได้มานั้นมีค่าน้อยกว่าความกว้างของตารางโจทย์หรือไม่ ถ้าหากน้อยกว่าจึงตอบจำนวนสีที่ได้มานั้นเป็นผลเฉลยออกมาได้เลย แต่ถ้าหากมากกว่าแสดงว่าโจทย์นี้ไม่สามารถแก้ได้
ทฤษฎีที่เกี่ยวข้อง
อ้างอิง Marx, Dániel (2004), "Graph colouring problems and their applications in scheduling", Periodica Polytechnica, Electrical Engineering , 48 , pp. 11–16 Björklund, A.; Husfeldt, T.; Koivisto, M. (2009), "Set partitioning via inclusion–exclusion", SIAM Journal on Computing , 39 (2): 546–563, doi :10.1137/070683933 Khot, S. (2001), "Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring", Proc. 42nd Annual Symposium on Foundations of Computer Science , pp. 600–609, doi :10.1109/SFCS.2001.959936
แหล่งข้อมูลอื่น การระบายสีจุดของกราฟ จากเว็บ ครูบ้านนอกดอตคอม (ไทย) ปัญหาการระบายสีกราฟ จากสารานุกรมไทยสำหรับเยาวชน (ไทย)
การระบายส, กราฟ, ญหาท, ได, บความสนใจอย, างมากในเร, องทฤษฎ, กราฟ, ญหา, งกฤษ, graph, coloring, problem, งเป, นป, ญหาท, เก, ยวก, บการพยายามระบายส, ดของกราฟ, โดยให, ดท, อย, ดก, นม, างก, นและใช, ให, อยท, ดการระบายส, บนจ, ดยอดของกราฟโดยจ, ดยอดท, เส, นเช, อมถ, งก, นใ. pyhathiidrbkhwamsnicxyangmakineruxngthvsdikraf khux pyhakarrabaysikraf xngkvs Graph coloring problem sungepnpyhathiekiywkbkarphyayamrabaysicudkhxngkraf odyihcudthixyutidknmisitangknaelaichsiihnxythisudkarrabaysibncudyxdkhxngkrafodycudyxdthimiesnechuxmthungknichsiimsakn inkrnikrafnitxngichsiepnxyangnxy 3 si karrabaysikrafxacmihlayrupaebb bangrupsamarthichsiephiyngsxngsikephiyngphxthicaihcudthixyutidknmisitangkn bangrupcaepntxngichhlaysithungcaephiyngphxthicaihcudthixyutidknmisitangkn dngnncaeriykcanwnsixyangnxythisudthiephiyngphxthicaihcudthixyutidknmisitangknwa canwnsikhxngkraf enuxha 1 prawti 2 bthniyamthiekiywkhxng 3 khntxnwithi 3 1 kartdsinic Decision 3 2 karhakhaehmaasmthisud Optimization 3 3 karnb Counting 4 karprayuktich 4 1 pyhakarkahndtarangewla Scheduling problem 4 2 pyhaekm Sudoku 5 thvsdithiekiywkhxng 6 xangxing 7 aehlngkhxmulxunprawti aekikhsaehtuhnungthithaihpyhaekiywkbkarrabaysicudkhxngkrafidrbkhwamsnicsuksakhnkhwaepnxnma idaek khwamekiywkhxngknrahwangpyhaechnnikbpyhakarrabaysiaephnthi odyimihenuxthisungmiesnekhtaednrwmknmisiediywkn eraxacphicarnaihehnkhwamekiywkhxngxnniidimyaknktwxyangechninaephnthi thaaethncnghwdtang dwycud aelwlakesnoyngcudsungaethncnghwdthimiesnekhtaednrwmkn erakcaidkrafkhxngaephnthiniipichinkaraekpyhakarrabaysiaephnthi sungcaehnidwapyhakarrabaysiaephnthikbpyhakarrabaysicudkhxngkraf epnpyhaediywkn nxkcaknikarrabaysiaephnthinn hlaytxhlaykhnechuxknwasamarthichsiephiyngsisikephiyngphxthicarabayaephnthiid ihenuxthithimiesnekhtaednrwmknmisitangknidesmx imwaenuxthitang inaephnthinncaeriyngrayknxyuxyangir sungnkkhnitsastridphyayamkhnkhwahakhatxbwa eruxngthihlaykhnechuxknnicringhruxim karkhbkhidpyhaninkkhnitsastridthaknmaepnewlanankwarxypicungmiphuphisucnidwakhwamechuxdngklawthuktxngbthniyamthiekiywkhxng aekikhrngkhelkh Chromatic number x G khuxcanwnthibxkwakraf G nntxngkarsinxythisudethaihrephuxrabaybnpmthnghmdinkraf rngkhphhunam Chromatic polynomial canwnwithiinkarlngsikraf G odyichcanwnsiimmakipkwa canwnsithiihma karrabaysiesnechuxm Edge coloring mikhwamkhlaykhlungkbkarrabaysipm aetcaepnkarrabaysilngbnesnechuxminkrafaethn sungmikhxcakdwaesnechuxmthitxkbpmediywkn catxngmisitangknkhntxnwithi aekikhkartdsinic Decision aekikh Input kraf G sungmipmepncanwn v pm canwnsiepncanwnetm k si Output khakhwamcringwakraf G lngsiiddwycanwnsinxykwahruxethakb k sihruxim ewlainkarthangan O 2nn khwamsbsxn exnphibriburnkarhakhaehmaasmthisud Optimization aekikh Input kraf G sungmipmepncanwn v pm Output rngkhelkhkhxngkraf G ewlainkarthangan O n log n 3 log log n 2 khwamsbsxn exnphiyakkarnb Counting aekikh Input kraf G sungmipmepncanwn v pm canwnsiepncanwnetm k si Output rngkhphhunamkhxngkraf G ewlainkarthangan O 2nn khwamsbsxn charpphibriburnkarprayuktich aekikhpyhakarrabaysikrafsamarthnaipichaekpyhatang inchiwitpracawnidxyangmakmay echn pyhakarkahndtarangewla Scheduling problem aekikh pyhanikhuxkarnanganhlay nganmacderiyngisinchwngewlathiwangxyu odyngantang catxngkarwtthudibechphaanganaelanganthitxngkarwtthudibediywkncaimsamarthkrathaphrxmknidinewlaidewlahnung michanncaekidkhwamsasxn cungtxngxasytarangewla ephuxchwyinkarkahndladbkarthangankxnhlngkhxngnganehlann Input estkhxngnganthitxnglngintarang Output ewlathinxythisudthiichinkarthanganehlanncnesrc odyimekidkhwamsasxn karaekpyhanidwykarrabaysikrafthaidodykaraethnngandwypmkhxngkraf aelalakesnechuxmnganthitxngichwtthudibediywkniwdwykn caknnthakarrabaysikraf phlthiidkkhuxcanwnsithinxysudthitxngich sungkkhuxrayaewlathinxythisudthisamarththanganthnghmdidnnexngpyhaekm Sudoku aekikh Input tarangocthyekm Sudoku Output khatxbkhxngocthykhxnn karaekpyha Sudoku dwykarrabaysikrafthaidodykaraethnchxngintarangdwypmkhxngkraf aelwlakesnechuxmchxngintarangthihammielkhsakntamkdkhxng Sudoku iwdwykn caknntrwcsxbwacanwnsithiidmannmikhanxykwakhwamkwangkhxngtarangocthyhruxim thahaknxykwacungtxbcanwnsithiidmannepnphlechlyxxkmaidely aetthahakmakkwaaesdngwaocthyniimsamarthaekidthvsdithiekiywkhxng aekikhthvsdikraf thvsdibthsisi thvsdibthhasixangxing aekikhMarx Daniel 2004 Graph colouring problems and their applications in scheduling Periodica Polytechnica Electrical Engineering 48 pp 11 16 Bjorklund A Husfeldt T Koivisto M 2009 Set partitioning via inclusion exclusion SIAM Journal on Computing 39 2 546 563 doi 10 1137 070683933 Khot S 2001 Improved inapproximability results for MaxClique chromatic number and approximate graph coloring Proc 42nd Annual Symposium on Foundations of Computer Science pp 600 609 doi 10 1109 SFCS 2001 959936aehlngkhxmulxun aekikhkarrabaysicudkhxngkraf cakewb khrubannxkdxtkhxm ithy pyhakarrabaysikraf caksaranukrmithysahrbeyawchn ithy ekhathungcak https th wikipedia org w index php title karrabaysikraf amp oldid 4701360, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
บทความ , อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม
