ทฤษฎีกราฟ - วิกิพีเดีย

# ทฤษฎีกราฟ

### จากวิกิพีเดีย สารานุกรมเสรี

กราฟที่มีจุดยอด 6 จุด และเส้นเชื่อม 7 เส้น

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

## [แก้] ประวัติ

ทฤษฎีกราฟนั้น มีจุดเริ่มจากผลงานตีพิมพ์ของ เลออนฮาร์ด ออยเลอร์ ภายใต้ชื่อ 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 แล้ว สมาชิก Mx,y จะเป็น 1 ไม่เช่นนั้น จะเป็น 0 ซึ่งทำให้ง่ายต่อการหากราฟย่อย และกราฟย้อนกลับ
- เมตริกซ์แบบลาปลาส (Laplacian matrix หรือ admittance matrix)

## [แก้] ทฤษฎีบทและปัญหาบนกราฟ

### [แก้] การค้นหากราฟย่อย

- ปัญหากลุ่มพรรคพวก - การค้นหากราฟย่อยที่เป็นกราฟบริบูรณ์ที่มีขนาดใหญ่ที่สุด กราฟย่อยดังกล่าวเรียกว่ากลุ่มพรรคพวก (clique)
- ปัญหาเซตอิสระ - การค้นหาเซตอิสระที่ใหญ่ที่สุด

### [แก้] การระบายสีกราฟ

- ทฤษฎีบทสี่สี

### [แก้] ปัญหาเส้นทาง

- ปัญหาสะพานทั้งเจ็ดแห่งเมืองโคนิกส์เบิร์ก
- ปัญหาวิถีสั้นสุด

### [แก้] การไหลในเครือข่าย

- การไหลในเครือข่าย

### [แก้] ปัญหากราฟการมองเห็น

- ปัญหายามเฝ้าพิพิธภัณฑ์

## [แก้] ดูเพิ่ม

- อภิธานศัพท์ทฤษฎีกราฟ

## [แก้] ดูเพิ่ม

- J.A. Bondy and U.S.R. Murty, Graph Theory with Applications [1]
- Reinhard Diestel, Graph Theory Third Edition [2]
- Lawler E.L., Combinatorial optimization.. networks and matroids [3]
- Einführung in Graphen und Algorithmen [4]

ดึงข้อมูลจาก "http://th.wikipedia.org../../../%E0%B8%97/%E0%B8%A4/%E0%B8%A9/%E0%B8%97%E0%B8%A4%E0%B8%A9%E0%B8%8E%E0%B8%B5%E0%B8%81%E0%B8%A3%E0%B8%B2%E0%B8%9F.html".

หมวดหมู่: ทฤษฎีกราฟ | วิยุตคณิต

##### Views

- บทความ
- อภิปราย
- รุ่นปัจจุบัน

##### ค้นหา

##### ภาษาอื่น

- Aragonés
- العربية
- Български
- Bosanski
- Česky
- Dansk
- Deutsch
- English
- Esperanto
- Español
- فارسی
- Suomi
- Français
- עברית
- Magyar
- Bahasa Indonesia
- Italiano
- 日本語
- 한국어
- Lietuvių
- Nederlands
- ‪Norsk (nynorsk)‬
- ‪Norsk (bokmål)‬
- Polski
- Português
- Русский
- Simple English
- Slovenčina
- Slovenščina
- Српски / Srpski
- Svenska
- Türkçe
- Українська
- Tiếng Việt
- 中文