ประวัติ ทฤษฎีกราฟนั้น มีจุดเริ่มจากผลงานตีพิมพ์ของ เลออนฮาร์ด ออยเลอร์ ภายใต้ชื่อ Solutio problematis ad geometriam situs pertinentis ในปี ค.ศ. 1736 (พ.ศ. 2279 ) หรือที่รู้จักกันในนาม ปัญหาสะพานทั้งเจ็ดแห่งเมืองโคนิกส์เบิร์ก ทอพอโลยี ชิ้นแรกในเรขาคณิต กล่าวคือเป็นงานที่สนใจเฉพาะโครงสร้างของรูปเรขาคณิตที่ไม่ขึ้นกับขนาด ระยะ หรือการวัดใดๆ งานชิ้นสำคัญนี้ยังได้แสดงความเกี่ยวข้องอย่างลึกซึ้งระหว่างทฤษฎีกราฟและทอพอโลยี
ในปี ค.ศ. 1845 (พ.ศ. 2388 ) กุสตาฟ คีร์คฮอฟฟ์ ได้เผยแพร่ผลงานที่รู้จักกันภายใต้ชื่อกฎวงจรไฟฟ้าของคีร์คฮอฟฟ์ ที่แสดงความสัมพันธ์ของกระแส และความต่างศักย์ บนกราฟที่แทนวงจรไฟฟ้า
ต่อมาในปี ค.ศ. 1852 (พ.ศ. 2395 ) ฟรานซิส กัทธรี ได้ตั้งปัญหาสี่สี พ.ศ. 2519 ) โดย เคนเนธ แอปเพล และวูล์ฟกัง ฮาเคน ซึ่งใช้คอมพิวเตอร์เข้าช่วยในการพิสูจน์ ซึ่งทำให้ได้รับการวิพากษ์วิจารณ์อย่างกว้างขวาง. อย่างไรก็ตามจากความพยายามในการแก้ปัญหา 4 สีนี้ ทำให้มีการสร้างแนวคิดและนิยามพื้นฐานในทฤษฎีกราฟขึ้นอย่างมากมาย จนอาจจะกล่าวได้ว่าจุดเริ่มต้นของทฤษฎีกราฟเกิดจากปัญหาสี่สีนี้เอง
กราฟมักถูกนำเสนอในลักษณะของรูปภาพ โดยใช้จุดแทนจุดยอดแต่ละจุด และลากเส้นระหว่างจุดยอดถ้าจุดยอดทั้งสองนั้นมีเส้นเชื่อมถึงกัน ถ้ากราฟมีทิศทาง ทิศทางของเส้นเชื่อมจะถูกระบุโดยใช้ลูกศร
เราไม่ควรจะสับสนระหว่างกราฟที่วาดออกมากับกราฟ (ที่เป็นโครงสร้างนามธรรม) เนื่องจากกราฟหนึ่ง ๆ สามารถเขียนออกมาได้หลายแบบ และสาระหลักของกราฟนั้นมีแค่ว่าจุดยอดใด เชื่อมต่อกับจุดยอดใด ด้วยเส้นเชื่อมกี่เส้น ไม่ใช่วิธีการที่วาดมันออกมา ในทางปฏิบัติแล้ว การจะตัดสินว่ากราฟที่วาดออกมาสองกราฟนั้น มาจากกราฟเดียวกัน ในบางกรณี การวาดกราฟบางแบบอาจมีความเหมาะสมและทำให้เข้าใจได้ง่ายกว่าแบบอื่น
โครงสร้างข้อมูลกราฟ มีหลายวิธีในการจัดเก็บกราฟในระบบคอมพิวเตอร์ โดยโครงสร้างข้อมูล ที่ใช้ขึ้นอยู่กับโครงสร้างของกราฟ และขั้นตอนวิธี สำหรับประมวลผลกราฟนั้น ในทางทฤษฎีเราอาจแยกแยะโครงสร้างที่เป็นแบบรายการกับที่เป็นเมทริกซ์ได้ แต่ในทางปฏิบัติมักพบว่าโครงสร้างที่ดีมักเป็นลูกผสมของโครงสร้างทั้งสองแบบ โครงสร้างแบบรายการนั้นมักใช้ในกรณีของกราฟเบาบาง (sparse graph) เนื่องจากมีการใช้หน่วยความจำที่น้อยกว่า ในทางกลับกันโครงสร้างแบบเมทริกซ์นั้น มีการเข้าถึงที่รวดเร็วกว่า แต่ก็ใช้หน่วยความจำขนาดใหญ่ถ้าจำนวนจุดยอดของกราฟมีมาก
โครงสร้างแบบรายการ รายการตกกระทบ (incidence list)รายการประชิด โครงสร้างแบบเมทริกซ์ เมทริกซ์ตกกระทบ (incidence matrix) - เป็นการจัดเก็บกราฟในเมทริกซ์ขนาด E (จำนวนเส้นเชื่อม) คูณ V (จำนวนจุดยอด) ซึ่ง [เส้นเชื่อม, จุดยอด] จะบรรจุข้อมูลของเส้นเชื่อมนั้น (เช่น 1 คือ เชื่อมต่อกัน, 0 คือ ไม่เชื่อมต่อกัน)เมตริกซ์ประชิด M x , y {\displaystyle M_{x,y}} เมตริกซ์แบบลาปลัส (Laplacian matrix หรือ admittance matrix)
การจำแนกชนิดของกราฟ ตามลักษณะข้อมูลที่เก็บ กราฟแบบมีทิศทาง (directed graph) และ กราฟแบบไม่มีทิศทาง (undirected graph) กราฟแบบมีน้ำหนัก (weighted graph) และ กราฟแบบไม่มีน้ำหนัก (unweighted graph) ตามการเชื่อมโยง กราฟสมบูรณ์ (complete graph) กราฟต่อเนื่อง (connected graph) กราฟไม่ต่อเนื่อง (unconnected graph) ต้นไม้ (โครงสร้างข้อมูล) (tree)
ทฤษฎีบทและปัญหาบนกราฟ การค้นหากราฟย่อย การระบายสีกราฟ ปัญหาเส้นทาง การไหลในเครือข่าย ปัญหากราฟการมองเห็น
ดูเพิ่ม
ดูเพิ่ม 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 ที่ เวย์แบ็กแมชชีน
ทฤษฎ, กราฟ, อม, ลเพ, มเต, กราฟ, คณ, ตศาสตร, และ, อภ, ธานศ, พท, งกฤษ, graph, theory, เป, นหน, งในสาขาคณ, ตศาสตร, และว, ทยาการคอมพ, วเตอร, กษาถ, งค, ณสมบ, าง, ของกราฟกราฟท, ดยอด, และเส, นเช, อม, เส, เน, อหา, ประว, โครงสร, างข, อม, ลกราฟ, โครงสร, างแบบรายการ, โคร. khxmulephimetim kraf khnitsastr aela xphithansphththvsdikraf thvsdikraf xngkvs graph theory epnhnunginsakhakhnitsastraelawithyakarkhxmphiwetxr thisuksathungkhunsmbtitang khxngkrafkrafthimicudyxd 6 cud aelaesnechuxm 7 esn enuxha 1 prawti 2 okhrngsrangkhxmulkraf 2 1 okhrngsrangaebbraykar 2 2 okhrngsrangaebbemthriks 3 karcaaenkchnidkhxngkraf 4 thvsdibthaelapyhabnkraf 4 1 karkhnhakrafyxy 4 2 karrabaysikraf 4 3 pyhaesnthang 4 4 karihlinekhruxkhay 4 5 pyhakrafkarmxngehn 5 duephim 6 duephimprawti aekikhthvsdikrafnn 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 nganchinsakhyniyngidaesdngkhwamekiywkhxngxyangluksungrahwangthvsdikrafaelathxphxolyiinpi kh s 1845 ph s 2388 kustaf khirkhhxff idephyaephrphlnganthiruckknphayitchuxkdwngcriffakhxngkhirkhhxff thiaesdngkhwamsmphnthkhxngkraaesaelakhwamtangsky bnkrafthiaethnwngcriffatxmainpi kh s 1852 ph s 2395 fransis kththri idtngpyhasisi Four color problem ephuxsuksathungkhwamepnipidthicaichsiephiyng 4 si ephuxrabayihkbpraethstang bnaephnthiid odythipraethsephuxnbancaimmisiediywkn pyhaniidthukaekinxikmakkwa 100 pithdma inpi kh s 1976 ph s 2519 ody ekhnenth aexpephl aelawulfkng haekhn sungichkhxmphiwetxrekhachwyinkarphisucn sungthaihidrbkarwiphakswicarnxyangkwangkhwang xyangirktamcakkhwamphyayaminkaraekpyha 4 sini thaihmikarsrangaenwkhidaelaniyamphunthaninthvsdikrafkhunxyangmakmay cnxaccaklawidwacuderimtnkhxngthvsdikrafekidcakpyhasisiniexngkrafmkthuknaesnxinlksnakhxngrupphaph odyichcudaethncudyxdaetlacud aelalakesnrahwangcudyxdthacudyxdthngsxngnnmiesnechuxmthungkn thakrafmithisthang thisthangkhxngesnechuxmcathukrabuodyichluksreraimkhwrcasbsnrahwangkrafthiwadxxkmakbkraf thiepnokhrngsrangnamthrrm enuxngcakkrafhnung samarthekhiynxxkmaidhlayaebb aelasarahlkkhxngkrafnnmiaekhwacudyxdid echuxmtxkbcudyxdid dwyesnechuxmkiesn imichwithikarthiwadmnxxkma inthangptibtiaelw karcatdsinwakrafthiwadxxkmasxngkrafnn macakkrafediywkn inbangkrni karwadkrafbangaebbxacmikhwamehmaasmaelathaihekhaicidngaykwaaebbxunokhrngsrangkhxmulkraf aekikhdubthkhwamhlkthi kraf okhrngsrangkhxmul mihlaywithiinkarcdekbkrafinrabbkhxmphiwetxr odyokhrngsrangkhxmulthiichkhunxyukbokhrngsrangkhxngkraf aelakhntxnwithisahrbpramwlphlkrafnn inthangthvsdieraxacaeykaeyaokhrngsrangthiepnaebbraykarkbthiepnemthriksid aetinthangptibtimkphbwaokhrngsrangthidimkepnlukphsmkhxngokhrngsrangthngsxngaebb okhrngsrangaebbraykarnnmkichinkrnikhxngkrafebabang sparse graph enuxngcakmikarichhnwykhwamcathinxykwa inthangklbknokhrngsrangaebbemthriksnn mikarekhathungthirwderwkwa aetkichhnwykhwamcakhnadihythacanwncudyxdkhxngkrafmimak okhrngsrangaebbraykar aekikh raykartkkrathb incidence list raykarprachid adjacency list okhrngsrangaebbemthriks aekikh emthrikstkkrathb 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 M x y displaystyle M x y caepn 1 imechnnn caepn 0 sungthaihngaytxkarhakrafyxy aelakrafyxnklb emtriksaebblapls Laplacian matrix hrux admittance matrix karcaaenkchnidkhxngkraf aekikhtamlksnakhxmulthiekbkrafaebbmithisthang 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 thvsdibthaelapyhabnkraf aekikhkarkhnhakrafyxy aekikh pyhaklumphrrkhphwk karkhnhakrafyxythiepnkrafbriburnthimikhnadihythisud krafyxydngklaweriykwaklumphrrkhphwk clique pyhaestxisra karkhnhaestxisrathiihythisudkarrabaysikraf aekikh thvsdibthsisipyhaesnthang aekikh pyhasaphanthngecdaehngemuxngokhniksebirk Euler circuit pyhawithisnsud Shortest path problem karwiekhraahesnthangwikvt Critical path analysis karihlinekhruxkhay aekikh karihlinekhruxkhaypyhakrafkarmxngehn aekikh pyhayamefaphiphithphnthduephim aekikhxphithansphththvsdikrafduephim aekikhJ A Bondy and U S R Murty Graph Theory with Applications 1 Archived 2010 04 13 thi ewyaebkaemchchin Reinhard Diestel Graph Theory Third Edition 2 Lawler E L Combinatorial optimization networks and matroids 3 Archived 2009 02 19 thi ewyaebkaemchchin Einfuhrung in Graphen und Algorithmen 4 Archived 2005 03 05 thi ewyaebkaemchchinekhathungcak https th wikipedia org w index php title thvsdikraf amp oldid 9644636, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
บทความ , อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม
