กราฟ (คณิตศาสตร์)
จากวิกิพีเดีย สารานุกรมเสรี
- บทความนี้มีรายละเอียดเฉพาะนิยามทั่วไปเท่านั้น สำหรับรายละเอียดอื่นๆ ดู: ทฤษฎีกราฟ
- สำหรับความหมายอื่นในทางคณิตศาสตร์ ดู: กราฟของฟังก์ชัน, กราฟของความสัมพันธ์
ในคณิตศาสตร์และวิทยาการคอมพิวเตอร์ กราฟ คือวัตถุพื้นฐานของการศึกษาในทฤษฎีกราฟ กล่าวอย่างไม่เป็นทางการได้ว่า, กราฟคือเซตของวัตถุที่เรียกว่า จุดยอด (vertex) ซึ่งเชื่อมต่อกันด้วย เส้นเชื่อม (edge) โดยทั่วไปแล้วเรามักวาดรูปแสดงกราฟโดยใช้เซตของจุด (แทนจุดยอด) เชื่อมกันด้วยเส้น (แทนเส้นเชื่อม) ในบางการประยุกต์ใช้งาน เส้นเชื่อมอาจแสดงอย่างมีทิศทางได้
สารบัญ |
[แก้] นิยาม
การให้นิยามในทฤษฎีกราฟมีความแตกต่างกันบ้าง ด้านล่างนี้คือมาตรฐานที่ใช้ในสารานุกรมนี้
[แก้] กราฟไม่ระบุทิศทาง
กราฟไม่ระบุทิศทาง หรือ กราฟ G คือคู่อันดับ G:=(V, E) ที่
- V คือ เซต ของ จุดยอด (vertices) หรือ จุด (nodes)
- E คือ เซตของคู่ของจุดยอดที่แตกต่างกัน ซึ่งแต่ละอันเรียกว่า เส้นเชื่อม (edges) หรือ เส้น (lines)
- จุดยอดที่ติดกับเส้นเชื่อมเรียกว่า จุดยอดปลาย (end vertices) ของเส้นเชื่อม
[แก้] กราฟระบุทิศทาง
กราฟระบุทิศทาง หรือ ไดกราฟ G คือคู่อันดับ G:=(V, A) ที่
- V คือ เซต ของ จุดยอด (vertices) หรือ จุด (nodes)
- A คือ เซตของคู่ลำดับของจุดยอด ซึ่งแต่ละอันเรียกว่า เส้นเชื่อมระบุทิศทาง (directed edges), เส้นเชื่อม (arcs) หรือ ลูกศร (arrows). เส้นเชื่อม e = (x, y) จะถูกพิจารณาว่าเป็นเส้นเชื่อม จาก x ไป y โดยที่ y จะถูกเรียกว่า หัว (head) และ x จะถูกเรียกว่า หาง (tail) ของเส้นเชื่อม
กราฟอวัฏจักรระบุทิศทาง (directed acyclic graph) หรือเรียกอีกอย่างว่า DAG คือ กราฟระบุทิศทาง ที่ไม่มีวัฏจักรระบุทิศทาง
[แก้] กราฟผสม
กราฟผสม G คือ สามสิ่งอันดับ (3-tuple) G:=(V,E,A) ที่ V, E และ A เหมือนดังนิยามด้านบน
[แก้] การนิยามที่แตกต่างไป
จากนิยามข้างต้น เส้นเชื่อมในกราฟไม่มีทิศทางจะต้องมีจุดปลายที่แตกต่างกัน นอกจากนี้ E และ A ยังเป็นเซต (ที่มีสมาชิกแตกต่างกัน) อย่างไรก็ตามในหลายๆ การประยุกต์ใช้ เราจะใช้นิยามที่กว้างกว่านี้
เราสามารถมี วงวน (loop) ที่หมายถึงเส้นเชื่อมที่มีจุดปลายเป็นจุดเดียวกัน ซึ่งการอนุญาตให้มีวงวนหรือไม่ขึ้นกับแต่ละการประยุกต์ใช้งาน
บางครั้ง E หรือ A สามารถเป็นมัลติเซต ซึ่งทำให้มีเส้นเชื่อมจุดปลายคู่ใด ๆ มากกว่าหนึ่งเส้นได้ เมื่อกล่าวถึง "กราฟ" ผู้เขียนอาจหมายถึงกราฟที่อนุญาตให้มีเส้นเชื่อมซ้ำกันหรือไม่ก็ได้ อย่างไรก็ตาม ถ้าต้องการระบุให้ชัดเจนว่ากราฟนั้นไม่มีเส้นเชื่อมซ้ำกัน จะเรียกกราฟนั้นว่ากราฟ กราฟเชิงเดียว (simple graph) ในทางกลับกันสำหรับกราฟที่อนุญาตให้มีเส้นเชื่อมซ้ำกันได้จะเรียกกราฟนั้นว่า มัลติกราฟ (multigraph) บางครั้งก็มีการใช้คำว่า กราฟจำลอง เพื่อระบุว่ากราฟสามารถมีได้ทั้งเส้นเชื่อมซ้ำและวงวน
[แก้] คุณลักษณะของกราฟ
เราจะกล่าวว่า
- เส้นเชื่อมสองเส้น ประชิด (adjacent) กัน ถ้าเส้นเชื่อมทั้งสองมีจุดปลายร่วมกัน
- จุดยอดสองจุด ประชิด กัน ถ้าจุดยอดทั้งสองเป็นจุดปลายของเส้นเชื่อมเดียวกัน
- เส้นเชื่อม ต่อ (incident) กับจุดปลายของเส้นเชื่อมเสมอ
กราฟที่มีจุดยอดเพียงจุดเดียวและไม่มีเส้นเชื่อมใดๆ เรียกว่า กราฟชัีด (trivial graph) กราฟที่มีแต่จุดยอดแต่ไม่มีเส้นเชื่อมใดๆ เรียกว่า กราฟว่าง (empty graph) ส่วนกราฟที่ไม่มีทั้งจุดยอดและเส้นเชื่อม เรียกว่า กราฟสูญ (null graph) แต่นิยามนี้ไม่เป็นที่นิยมนัก
กราฟถ่วงน้ำหนัก (weighted graph) คือ กราฟที่มีการกำหนดค่าให้กับเส้นเชื่อมแต่ละเส้น ซึ่งอาจเป็น ค่าใช้จ่าย, น้ำหนัก, ความยาว หรืออื่นๆขึ้นกับการใช้งาน กราฟถ่วงน้ำหนักนำไปใช้ในการแก้ปัญหาหลายๆอย่าง เช่น ปัญหาเส้นทางที่ดีที่สุด เป็นต้น
โดยทั่วไปแล้วจุดยอดของกราฟนั้นจะไม่สามารถถูกแยกแยะ หรือพิจารณาว่าแตกต่างกันได้ (ยกเว้นในบางกรณีเช่นมีจำนวนเส้นเชื่อมที่แตกต่างกันเป็นต้น) อย่างไรก็ตาม บางสาขาของทฤษฎีกราฟต้องการให้ระบุจุดยอดที่ชัดเจนได้ ถ้าแต่ละจุดยอดมีการระบุชื่อที่ชัดเจน (มี label) กำกับ เราจะเรียกกราฟเหล่านั้นนั้นว่า กราฟระบุชื่อ (labeled graph) ในกรณีที่ไม่มีการระบุชื่อจะเรียกกราฟว่า กราฟไม่ระบุชื่อ
[แก้] ตัวอย่าง
จากรูปทางขวา เขียนเป็นกราฟได้ดังนี้
- V:={1,2,3,4,5,6}
- E:={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}
- ในทฤษฎีประเภท ประเภทสามารถพิจารณาเป็นกราฟระบุทิศทาง โดยที่วัตถุที่กล่าวถึงจะเป็นจุดยอด และสัณฐาน (morphism) เป็นเส้นเชื่อมระบุทิศทาง ด้วยการแสดงเช่นนี้ ฟังก์เตอร์ระหว่างสองประเภทคือสัณฐานของกราฟ
- ในวิทยาการคอมพิวเตอร์ กราฟระบุทิศทางมักใช้แสดง เครื่องจักรสถานะจำกัด และโครงสร้างอีกหลาย ๆ แบบ
[แก้] กราฟที่สำคัญ
- กราฟบริบูรณ์ (complete graph) คือ กราฟที่ทุก ๆ คู่ของจุดยอดจะถูกเชื่อมด้วยเส้นเชื่อม ดังนั้น กราฟนี้จะมีเส้นเชื่อมทุกเส้นที่เป็นไปได้
- กราฟเชิงระนาบ (planar graph) คือ กราฟที่สามารถเขียนบนระนาบได้ โดยไม่มีเส้นเชื่อมใดๆตัดกัน
- ต้นไม้ (tree) คือ กราฟเชื่อมโยงที่ไม่มีวัฏจักร
- กราฟสองส่วน (bipartite graph)
- กราฟสมบูรณ์ (Perfect graph)
- กราฟเส้น (Line graph)
- โคกราฟ (Cograph)
[แก้] นัยทั่วไปของกราฟ
ในไฮเปอร์กราฟ เส้นเชื่อมสามารถเชื่อมได้มากกว่าสองจุด
ทุก ๆ กราฟ ก่อให้เกิด เมทรอยด์ แต่โดยทั่วไปแล้ว เราจะไม่สามารถสร้างกราฟกลับมาจากเมทรอยด์ของมันได้ ดังนั้นเมทรอยด์จึงไม่ใช่นัยทั่วไปของกราฟ
ในทฤษฎีโมเดล กราฟเป็นแค่โครงสร้าง ในกรณีนั้นจะไม่มีข้อจำกัดในจำนวนของเส้นเชื่อม นั่นคือจะมีเส้นเชื่อมเป็นจำนวนเชิงการนับใด ๆ ก็ได้
