ในคณิตศาสตร์และวิทยาการคอมพิวเตอร์ กราฟ คือ วัตถุพื้นฐานของการศึกษาในทฤษฎีกราฟ กล่าวอย่างไม่เป็นทางการได้ว่า กราฟ คือ เซตของวัตถุที่เรียกว่า จุดยอด (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 คือ กราฟระบุทิศทาง ที่ไม่มีวัฏจักรระบุทิศทาง

กราฟผสม G คือ สามสิ่งอันดับ (3-tuple) G:=(V,E,A) ที่ V, E และ A เหมือนดังนิยามด้านบน

จากนิยามข้างต้น เส้นเชื่อมในกราฟไม่มีทิศทางจะต้องมีจุดปลายที่แตกต่างกัน นอกจากนี้ E และ A ยังเป็นเซต (ที่มีสมาชิกแตกต่างกัน) อย่างไรก็ตามในหลายๆ การประยุกต์ใช้ เราจะใช้นิยามที่กว้างกว่านี้

เราสามารถมี วงวน (loop) ที่หมายถึงเส้นเชื่อมที่มีจุดปลายเป็นจุดเดียวกัน ซึ่งการอนุญาตให้มีวงวนหรือไม่ขึ้นกับแต่ละการประยุกต์ใช้งาน

บางครั้ง E หรือ A สามารถเป็นมัลติเซต ซึ่งทำให้มีเส้นเชื่อมจุดปลายคู่ใด ๆ มากกว่าหนึ่งเส้นได้ เมื่อกล่าวถึง "กราฟ" ผู้เขียนอาจหมายถึงกราฟที่อนุญาตให้มีเส้นเชื่อมซ้ำกันหรือไม่ก็ได้ อย่างไรก็ตาม ถ้าต้องการระบุให้ชัดเจนว่ากราฟนั้นไม่มีเส้นเชื่อมซ้ำกัน จะเรียกกราฟนั้นว่ากราฟ กราฟเชิงเดียว (simple graph) ในทางกลับกันสำหรับกราฟที่อนุญาตให้มีเส้นเชื่อมซ้ำกันได้จะเรียกกราฟนั้น ว่า มัลติกราฟ (multigraph) บางครั้งก็มีการใช้คำว่า กราฟจำลอง เพื่อระบุว่ากราฟสามารถมีได้ทั้งเส้นเชื่อมซ้ำและวงวน

อ้างอิงจาก https://th.wikipedia.org/wiki/กราฟ_(คณิตศาสตร์)