ทฤษฎีกราฟ

ทฤษฎีกราฟ () เป็นหนึ่งในสาขาคณิตศาสตร์และวิทยาการคอมพิวเตอร์ ที่ศึกษาถึงคุณสมบัติต่าง ๆ ของกราฟ

ประวัติ 
ทฤษฎีกราฟนั้น มีจุดเริ่มจากผลงานตีพิมพ์ของ เลออนฮาร์ด ออยเลอร์ ภายใต้ชื่อ 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 แล้ว สมาชิก  จะเป็น 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  
 Reinhard Diestel, Graph Theory Third Edition 
 Lawler E.L., Combinatorial optimization.. networks and matroids   
 Einführung in Graphen und Algorithmen  

 
วิยุตคณิต