Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ทฤษฎีกราฟ (อังกฤษ: graph theory) เป็นหนึ่งในสาขาคณิตศาสตร์และวิทยาการคอมพิวเตอร์ ที่ศึกษาถึงคุณสมบัติต่าง ๆ ของกราฟ
ประวัติ
ทฤษฎีกราฟนั้น มีจุดเริ่มจากผลงานตีพิมพ์ของ เลออนฮาร์ด ออยเลอร์ ภายใต้ชื่อ Solutio problematis ad geometriam situs pertinentis ในปี ค.ศ. 1736 (พ.ศ. 2279) หรือที่รู้จักกันในนาม ปัญหาสะพานทั้งเจ็ดแห่งเมืองโคนิกส์เบิร์ก (Seven Bridges of Königsberg) เขาสนใจวิธีที่จะข้ามสะพานทั้ง 7 แห่งนี้ โดยข้ามแต่ละสะพานเพียงครั้งเดียวเท่านั้น ผลงานนี้ยังถือว่าเป็นงานแนวทอพอโลยีชิ้นแรกในเรขาคณิต กล่าวคือเป็นงานที่สนใจเฉพาะโครงสร้างของรูปเรขาคณิตที่ไม่ขึ้นกับขนาด ระยะ หรือการวัดใดๆ งานชิ้นสำคัญนี้ยังได้แสดงความเกี่ยวข้องอย่างลึกซึ้งระหว่างทฤษฎีกราฟและทอพอโลยี
ในปี ค.ศ. 1845 (พ.ศ. 2388) กุสตาฟ คีร์คฮอฟฟ์ ได้เผยแพร่ผลงานที่รู้จักกันภายใต้ชื่อ ที่แสดงความสัมพันธ์ของกระแสและความต่างศักย์ บนกราฟที่แทนวงจรไฟฟ้า
ต่อมาในปี ค.ศ. 1852 (พ.ศ. 2395) ได้ตั้งปัญหาสี่สี (Four color problem) เพื่อศึกษาถึงความเป็นไปได้ที่จะใช้สีเพียง 4 สี เพื่อระบายให้กับประเทศต่าง ๆ บนแผนที่ใด ๆ โดยที่ประเทศเพื่อนบ้านจะไม่มีสีเดียวกัน. ปัญหานี้ได้ถูกแก้ในอีกมากกว่า 100 ปีถัดมา ในปี ค.ศ. 1976 (พ.ศ. 2519) โดย และ ซึ่งใช้คอมพิวเตอร์เข้าช่วยในการพิสูจน์ ซึ่งทำให้ได้รับการวิพากษ์วิจารณ์อย่างกว้างขวาง. อย่างไรก็ตามจากความพยายามในการแก้ปัญหา 4 สีนี้ ทำให้มีการสร้างแนวคิดและนิยามพื้นฐานในทฤษฎีกราฟขึ้นอย่างมากมาย จนอาจจะกล่าวได้ว่าจุดเริ่มต้นของทฤษฎีกราฟเกิดจากปัญหาสี่สีนี้เอง
กราฟมักถูกนำเสนอในลักษณะของรูปภาพ โดยใช้จุดแทนจุดยอดแต่ละจุด และลากเส้นระหว่างจุดยอดถ้าจุดยอดทั้งสองนั้นมีเส้นเชื่อมถึงกัน ถ้ากราฟมีทิศทาง ทิศทางของเส้นเชื่อมจะถูกระบุโดยใช้ลูกศร
เราไม่ควรจะสับสนระหว่างกราฟที่วาดออกมากับกราฟ (ที่เป็นโครงสร้างนามธรรม) เนื่องจากกราฟหนึ่ง ๆ สามารถเขียนออกมาได้หลายแบบ และสาระหลักของกราฟนั้นมีแค่ว่าจุดยอดใด เชื่อมต่อกับจุดยอดใด ด้วยเส้นเชื่อมกี่เส้น ไม่ใช่วิธีการที่วาดมันออกมา ในทางปฏิบัติแล้ว การจะตัดสินว่ากราฟที่วาดออกมาสองกราฟนั้น มาจากกราฟเดียวกัน ในบางกรณี การวาดกราฟบางแบบอาจมีความเหมาะสมและทำให้เข้าใจได้ง่ายกว่าแบบอื่น
โครงสร้างข้อมูลกราฟ
มีหลายวิธีในการจัดเก็บกราฟในระบบคอมพิวเตอร์ โดยโครงสร้างข้อมูลที่ใช้ขึ้นอยู่กับโครงสร้างของกราฟ และขั้นตอนวิธีสำหรับประมวลผลกราฟนั้น ในทางทฤษฎีเราอาจแยกแยะโครงสร้างที่เป็นแบบรายการกับที่เป็นเมทริกซ์ได้ แต่ในทางปฏิบัติมักพบว่าโครงสร้างที่ดีมักเป็นลูกผสมของโครงสร้างทั้งสองแบบ โครงสร้างแบบรายการนั้นมักใช้ในกรณีของ (sparse graph) เนื่องจากมีการใช้หน่วยความจำที่น้อยกว่า ในทางกลับกันโครงสร้างแบบเมทริกซ์นั้น มีการเข้าถึงที่รวดเร็วกว่า แต่ก็ใช้หน่วยความจำขนาดใหญ่ถ้าจำนวนจุดยอดของกราฟมีมาก
โครงสร้างแบบรายการ
- (incidence list)
- รายการประชิด (adjacency list)
โครงสร้างแบบเมทริกซ์
- (incidence matrix) - เป็นการจัดเก็บกราฟในเมทริกซ์ขนาด E (จำนวนเส้นเชื่อม) คูณ V (จำนวนจุดยอด) ซึ่ง [เส้นเชื่อม, จุดยอด] จะบรรจุข้อมูลของเส้นเชื่อมนั้น (เช่น 1 คือ เชื่อมต่อกัน, 0 คือ ไม่เชื่อมต่อกัน)
- เมตริกซ์ประชิด (adjacency matrix) - เป็นการจัดเก็บกราฟในเมทริกซ์ขนาด N คูณ N เมื่อ N คือจำนวนของจุดยอดในกราฟ ถ้ามีเส้นเชื่อมจากจุดยอด x ไปจุดยอด y แล้ว สมาชิก
![image]()
จะเป็น 1 ไม่เช่นนั้น จะเป็น 0 ซึ่งทำให้ง่ายต่อการหากราฟย่อย และกราฟย้อนกลับ - (Laplacian matrix หรือ admittance matrix)
การจำแนกชนิดของกราฟ
- ตามลักษณะข้อมูลที่เก็บ
- กราฟแบบมีทิศทาง (directed graph) และ กราฟแบบไม่มีทิศทาง (undirected graph)
- กราฟแบบมีน้ำหนัก (weighted graph) และ กราฟแบบไม่มีน้ำหนัก (unweighted graph)
- ตามการเชื่อมโยง
- กราฟสมบูรณ์ (complete graph)
- กราฟต่อเนื่อง (connected graph)
- กราฟไม่ต่อเนื่อง (unconnected graph)
- ต้นไม้ (โครงสร้างข้อมูล) (tree)
ทฤษฎีบทและปัญหาบนกราฟ
การค้นหากราฟย่อย
- ปัญหากลุ่มพรรคพวก - การค้นหากราฟย่อยที่เป็นกราฟบริบูรณ์ที่มีขนาดใหญ่ที่สุด กราฟย่อยดังกล่าวเรียกว่า (clique)
- - การค้นหาเซตอิสระที่ใหญ่ที่สุด
การระบายสีกราฟ
ปัญหาเส้นทาง
- ปัญหาสะพานทั้งเจ็ดแห่งเมืองโคนิกส์เบิร์ก (Euler circuit)
- ปัญหาวิถีสั้นสุด (Shortest path problem)
- (Critical path analysis)
การไหลในเครือข่าย
ปัญหากราฟการมองเห็น
ดูเพิ่ม
ดูเพิ่ม
- J.A. Bondy and U.S.R. Murty, Graph Theory with Applications [1] 2010-04-13 ที่ เวย์แบ็กแมชชีน
- Reinhard Diestel, Graph Theory Third Edition [2]
- Lawler E.L., Combinatorial optimization.. networks and matroids [3] 2009-02-19 ที่ เวย์แบ็กแมชชีน
- Einführung in Graphen und Algorithmen [4] 2005-03-05 ที่ เวย์แบ็กแมชชีน
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
thvsdikraf xngkvs graph theory epnhnunginsakhakhnitsastraelawithyakarkhxmphiwetxr thisuksathungkhunsmbtitang khxngkrafkrafthimicudyxd 6 cud aelaesnechuxm 7 esnprawtithvsdikrafnn micuderimcakphlngantiphimphkhxng elxxnhard xxyelxr phayitchux Solutio problematis ad geometriam situs pertinentis inpi kh s 1736 ph s 2279 hruxthiruckkninnam pyhasaphanthngecdaehngemuxngokhniksebirk Seven Bridges of Konigsberg ekhasnicwithithicakhamsaphanthng 7 aehngni odykhamaetlasaphanephiyngkhrngediywethann phlnganniyngthuxwaepnnganaenwthxphxolyichinaerkinerkhakhnit klawkhuxepnnganthisnicechphaaokhrngsrangkhxngruperkhakhnitthiimkhunkbkhnad raya hruxkarwdid nganchinsakhyniyngidaesdngkhwamekiywkhxngxyangluksungrahwangthvsdikrafaelathxphxolyi inpi kh s 1845 ph s 2388 kustaf khirkhhxff idephyaephrphlnganthiruckknphayitchux thiaesdngkhwamsmphnthkhxngkraaesaelakhwamtangsky bnkrafthiaethnwngcriffa txmainpi kh s 1852 ph s 2395 idtngpyhasisi Four color problem ephuxsuksathungkhwamepnipidthicaichsiephiyng 4 si ephuxrabayihkbpraethstang bnaephnthiid odythipraethsephuxnbancaimmisiediywkn pyhaniidthukaekinxikmakkwa 100 pithdma inpi kh s 1976 ph s 2519 ody aela sungichkhxmphiwetxrekhachwyinkarphisucn sungthaihidrbkarwiphakswicarnxyangkwangkhwang xyangirktamcakkhwamphyayaminkaraekpyha 4 sini thaihmikarsrangaenwkhidaelaniyamphunthaninthvsdikrafkhunxyangmakmay cnxaccaklawidwacuderimtnkhxngthvsdikrafekidcakpyhasisiniexng krafmkthuknaesnxinlksnakhxngrupphaph odyichcudaethncudyxdaetlacud aelalakesnrahwangcudyxdthacudyxdthngsxngnnmiesnechuxmthungkn thakrafmithisthang thisthangkhxngesnechuxmcathukrabuodyichluksr eraimkhwrcasbsnrahwangkrafthiwadxxkmakbkraf thiepnokhrngsrangnamthrrm enuxngcakkrafhnung samarthekhiynxxkmaidhlayaebb aelasarahlkkhxngkrafnnmiaekhwacudyxdid echuxmtxkbcudyxdid dwyesnechuxmkiesn imichwithikarthiwadmnxxkma inthangptibtiaelw karcatdsinwakrafthiwadxxkmasxngkrafnn macakkrafediywkn inbangkrni karwadkrafbangaebbxacmikhwamehmaasmaelathaihekhaicidngaykwaaebbxunokhrngsrangkhxmulkrafmihlaywithiinkarcdekbkrafinrabbkhxmphiwetxr odyokhrngsrangkhxmulthiichkhunxyukbokhrngsrangkhxngkraf aelakhntxnwithisahrbpramwlphlkrafnn inthangthvsdieraxacaeykaeyaokhrngsrangthiepnaebbraykarkbthiepnemthriksid aetinthangptibtimkphbwaokhrngsrangthidimkepnlukphsmkhxngokhrngsrangthngsxngaebb okhrngsrangaebbraykarnnmkichinkrnikhxng sparse graph enuxngcakmikarichhnwykhwamcathinxykwa inthangklbknokhrngsrangaebbemthriksnn mikarekhathungthirwderwkwa aetkichhnwykhwamcakhnadihythacanwncudyxdkhxngkrafmimak okhrngsrangaebbraykar incidence list raykarprachid adjacency list okhrngsrangaebbemthriks incidence matrix epnkarcdekbkrafinemthrikskhnad E canwnesnechuxm khun V canwncudyxd sung esnechuxm cudyxd cabrrcukhxmulkhxngesnechuxmnn echn 1 khux echuxmtxkn 0 khux imechuxmtxkn emtriksprachid adjacency matrix epnkarcdekbkrafinemthrikskhnad N khun N emux N khuxcanwnkhxngcudyxdinkraf thamiesnechuxmcakcudyxd x ipcudyxd y aelw smachik Mx y displaystyle M x y caepn 1 imechnnn caepn 0 sungthaihngaytxkarhakrafyxy aelakrafyxnklb Laplacian matrix hrux admittance matrix karcaaenkchnidkhxngkraftamlksnakhxmulthiekbkrafaebbmithisthang directed graph aela krafaebbimmithisthang undirected graph krafaebbminahnk weighted graph aela krafaebbimminahnk unweighted graph tamkarechuxmoyngkrafsmburn complete graph kraftxenuxng connected graph krafimtxenuxng unconnected graph tnim okhrngsrangkhxmul tree thvsdibthaelapyhabnkrafkarkhnhakrafyxy pyhaklumphrrkhphwk karkhnhakrafyxythiepnkrafbriburnthimikhnadihythisud krafyxydngklaweriykwa clique karkhnhaestxisrathiihythisudkarrabaysikraf thvsdibthsisipyhaesnthang pyhasaphanthngecdaehngemuxngokhniksebirk Euler circuit pyhawithisnsud Shortest path problem Critical path analysis karihlinekhruxkhay karihlinekhruxkhaypyhakrafkarmxngehnduephimxphithansphththvsdikrafduephimJ A Bondy and U S R Murty Graph Theory with Applications 1 2010 04 13 thi ewyaebkaemchchin Reinhard Diestel Graph Theory Third Edition 2 Lawler E L Combinatorial optimization networks and matroids 3 2009 02 19 thi ewyaebkaemchchin Einfuhrung in Graphen und Algorithmen 4 2005 03 05 thi ewyaebkaemchchin