กราฟ (คณิตศาสตร์)

นิยาม

โดยทั่วไป กราฟ G คือคู่อันดับ G = (V, E) โดยที่ V คือเซตของจุดยอด และ E คือเซตของเส้นเชื่อมซึ่งเป็นคู่ไม่อันดับของจุดยอด อันที่จริงนิยามที่กล่าวไปเป็นเพียงประเภทหนึ่งของกราฟที่เรียกว่า กราฟไม่ระบุทิศทาง และเป็น กราฟอย่างง่าย
กราฟประเภทอื่นๆจะมีรายละเอียดของเซตเส้นเชื่อม (E) ที่แตกต่างกัน เช่น สังเกตว่านิยามข้างต้นจะไม่สามารถมีเส้นเชื่อมในกราฟสองเส้นที่เชื่อมจุดยอดสองจุดในลักษณะเดียวกันได้ เนื่องจาก E เป็นเซต ซึ่งสมาชิกที่เหมือนกันจะถูกมองเป็นเพียงแค่หนึ่งตัว หากเปลี่ยน E ให้กลายเป็นมัลติเซตก็จะได้สิ่งที่เรียกว่ามัลติกราฟหรือกราฟเทียมแทนกราฟปกติ ซึ่งรองรับเส้นเชื่อมหลายๆเส้นที่เชื่อมระหว่างจุดยอดสองจุดที่เหมือนกัน หรือที่เรียกว่า เส้นเชื่อมขนาน (เส้นเชื่อมสีแดงตามภาพด้านขวา)
สำหรับประเภทของกราฟต่างๆที่สมบูรณ์มากกว่านี้ โปรดดูข้างล่าง
จุดยอดที่อยู่ที่ปลายของเส้นเชื่อมจะเรียกว่าจุดยอดปลายของเส้นเชื่อม แต่จุดยอดอาจจะไม่เป็นจุดยอดปลายก็ได้ (ในกรณีที่จุดยอดนั้นไม่มีเส้นเชื่อมมาต่อเลย)
V และ E โดยปกติจะเป็นเซตจำกัด ถึงแม้ว่าจะเป็นไปได้ที่ V หรือ E จะเป็นเซตอนันต์ แต่นิยามหลายๆอย่างจะใช้ไม่ได้ในกรณีนั้น อันดับของกราฟคือ |V| (จำนวนจุดยอด) ส่วนขนาดของกราฟคือ |E| (จำนวนเส้นเชื่อม) ระดับขั้นของจุดยอดคือจำนวนของเส้นเชื่อมที่ต่อกับจุดยอดนั้นๆ ในกรณีที่มีเส้นเชื่อมที่ปลายสองด้านต่อเข้ากับจุดยอดเดียวกัน หรือที่เรียกว่าวงวน (เส้นเชื่อมสีน้ำเงินตามภาพด้านขวา) ให้นับระดับขั้นเพิ่ม 2 สำหรับ 1 วงวน
เส้นเชื่อม {u , v} อาจเขียนให้สั้นว่า uv ก็ได้..

ประเภทของกราฟ

ตามที่ได้กล่าวมาแล้วว่ากราฟมีหลายประเภท อย่างไรก็ตามกราฟในความหมายโดยทั่วไปจะหมายถึงกราฟไม่ระบุทิศทางอย่างง่ายและจำกัด

กราฟไม่ระบุทิศทาง

กราฟไม่ระบุทิศทาง (undirected graph) G คือคู่อันดับ G = (V, E) ที่ E คือ เซตของเส้นเชื่อมซึ่งเป็นคู่ไม่อันดับของจุดยอด e = {x, y} จะถูกพิจารณาว่าเป็นเส้นเชื่อม เชื่อมระหว่าง x กับ y โดยที่ทั้ง x และ y จะถูกเรียกว่า จุดยอดปลาย (end vertices) ของเส้นเชื่อม

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

กราฟระบุทิศทาง (directed graph) หรือ ไดกราฟ D คือคู่อันดับ D = (V, A) ที่ A คือ เซตของเส้นเชื่อมระบุทิศทางซึ่งเป็นคู่อันดับของจุดยอด เส้นเชื่อมระบุทิศทาง (directed edges) อาจถูกเรียกว่า อาร์ก (arcs) หรือ ลูกศร (arrows) เส้นเชื่อม e = (x, y) จะถูกพิจารณาว่าเป็นเส้นเชื่อม จาก x ไป y โดยที่ y จะถูกเรียกว่า หัว (head) และ x จะถูกเรียกว่า หาง (tail) ของเส้นเชื่อม เส้นเชื่อม (y, x) จะถูกเรียกว่าเป็นเส้นเชื่อมกลับทิศของ (x, y)
กราฟระบุทิศทาง D จะถูกเรียกว่า สมมาตร ก็ต่อเมื่อทุกๆเส้นเชื่อม (x,y) มีเส้นเชื่อม (y,x) อยู่ในกราฟด้วย ในแง่การไปถึงกันได้ กราฟระบุทิศทางที่สมมาตร D จะเทียบเท่ากับกราฟไม่ระบุทิศทาง G โดยเส้นเชื่อม (x,y) และ (y,x) เทียบเท่ากับเส้นเชื่อม {x,y} ดังนั้น หากเปรียบเทียบระหว่างกราฟระบุทิศทางที่สมมาตรและกราฟไม่ระบุทิศทาง ที่เทียบเท่ากัน จะได้ว่า |E| = |A|/2
กราฟอวัฏจักรระบุทิศทาง (directed acyclic graph: DAG) คือ กราฟระบุทิศทาง ที่ไม่มีวัฏจักร

กราฟผสม

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

กราฟอย่างง่าย

กราฟอย่างง่าย หรือ กราฟเชิงเดียว (simple graph) เป็นกราฟที่ไม่มี วงวน (loop) ซึ่งเกิดจากเส้นเชื่อมที่มีจุดเริ่มต้นเป็นจุดเดียวกับจุดปลาย และไม่มีเส้นเชื่อมขนาน (parallel edge) ซึ่งเกิดจากเส้นเชื่อมที่มีจุดเริ่มต้นและจุดปลายเหมือนกัน

มัลติกราฟ

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

แบ่งตามขนาด

กราฟ G = (V,E) จะเป็นกราฟจำกัด (finite graph) ก็ต่อเมื่อ V และ E เป็นเซตจำกัด
ในทางตรงกันข้าม หากมี V หรือ E อย่างใดอย่างหนึ่งที่เป็นเซตอนันต์ ก็จะได้ว่า G เป็นกราฟอนันต์ (infinite graph)

แบ่งตามน้ำหนัก

กราฟถ่วงน้ำหนัก (weighted graph) คือ กราฟที่มีการกำหนดค่าให้กับเส้นเชื่อมแต่ละเส้น ซึ่งอาจเป็น ค่าใช้จ่าย, น้ำหนัก, ความยาว หรืออื่นๆขึ้นกับการใช้งาน บางคนเรียกกราฟประเภทนี้ว่าเครือข่าย กราฟถ่วงน้ำหนักนำไปใช้ในการแก้ปัญหาหลายๆอย่าง เช่น ปัญหาวิถีสั้นสุด เป็นต้น โดยทั่วไปน้ำหนักที่ถ่วงจะถือว่าเป็นจำนวนจริงบวก ในกรณีที่น้ำหนักเส้นเชื่อมเป็นลบได้จะมีการระบุเพิ่มเติม เนื่องจากการจัดการกับกรณีทั้งสองในหลายๆปัญหานั้นต่างกัน
โดยทั่วไปหากกล่าวถึงกราฟจะหมายถึงกราฟไม่ถ่วงน้ำหนัก (unweighted graph) ซึ่งไม่มีน้ำหนักถ่วงที่เส้นเชื่อม

ในทั่วไปของกราฟ

ในไฮเปอร์กราฟ เส้นเชื่อมสามารถเชื่อมได้มากกว่าสองจุด
ทุก ๆ กราฟ ก่อให้เกิด เมทรอยด์ แต่โดยทั่วไปแล้ว เราจะไม่สามารถสร้างกราฟกลับมาจากเมทรอยด์ของมันได้ ดังนั้นเมทรอยด์จึงไม่ใช่นัยทั่วไปของกราฟ
ในทฤษฎีโมเดล กราฟเป็นแค่โครงสร้าง ในกรณีนั้นจะไม่มีข้อจำกัดในจำนวนของเส้นเชื่อม นั่นคือจะมีเส้นเชื่อมเป็นจำนวนเชิงการนับใด ๆ ก็ได้