กราฟ

บทความนี้เกี่ยวกับนิยามทั่วไปของกราฟ สำหรับรายละเอียดอื่น ๆ ดูที่ ทฤษฎีกราฟ

สำหรับความหมายอื่นในทางคณิตศาสตร์ ดูที่ กราฟของฟังก์ชัน และกราฟของความสัมพันธ์

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

ในคณิตศาสตร์และวิทยาการคอมพิวเตอร์ กราฟ คือ วัตถุพื้นฐานของการศึกษาในทฤษฎีกราฟ กล่าวอย่างไม่เป็นทางการได้ว่า กราฟ คือ เซตของวัตถุที่เรียกว่า จุดยอด (vertex) ซึ่งเชื่อมต่อกันด้วย เส้นเชื่อม (edge) โดยทั่วไปแล้วเรามักวาดรูปแสดงกราฟโดยใช้เซตของจุด (แทนจุดยอด) เชื่อมกันด้วยเส้น (แทนเส้นเชื่อม) ในบางการประยุกต์ใช้งาน เส้นเชื่อมอาจแสดงอย่างมีทิศทางได้

นิยาม
การให้นิยามในทฤษฎีกราฟมีความแตกต่างกันบ้าง ด้านล่างนี้คือมาตรฐานที่ใช้ในสารานุกรมนี้

กราฟไม่ระบุทิศทาง หรือ กราฟ G คือคู่อันดับ G:=(V, E) ที่

• V คือ เซต ของ จุดยอด (vertices) หรือ จุด (nodes)
• E คือ เซตของคู่ของจุดยอดที่แตกต่างกัน ซึ่งแต่ละอันเรียกว่า เส้นเชื่อม (edges) หรือ เส้น (lines)
• จุดยอดที่ติดกับเส้นเชื่อมเรียกว่า จุดยอดปลาย (end vertices) ของเส้นเชื่อม

กราฟระบุทิศทาง

กราฟระบุทิศทาง (directed graph) หรือ ไดกราฟ 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 คือ กราฟระบุทิศทาง ที่ไม่มีวัฏจักรระบุทิศทาง ห่วง (loop) เกิดจากอาร์กที่มีจุดเริ่มต้นเป็นจุดเดียวกับจุดปลาย ขนานกัน (parallel) เกิดจากอาร์กที่มีจุดเริ่มต้นเหมือนกัน และจุดปลายเหมือนกัน

กราฟผสม
กราฟผสม 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) ในกรณีที่ไม่มีการระบุชื่อจะเรียกกราฟว่า กราฟไม่ระบุชื่อ

ที่ทา wikipedia