กราฟ

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

เส้นเชื่อมอาจมีทิศทางหรือไม่ก็ได้ ตัวอย่างเช่น สมมุติให้จุดยอดแทนคนและเส้นเชื่อมแทนการจับมือกัน เส้นเชื่อมก็จะเป็นเส้นเชื่อมไม่มีทิศ เพราะการที่ A จับมือ B ก็แปลว่า B จับมือ Aอย่างไรก็ตาม สมมุติถ้าจุดยอดแทนคนและเส้นเชื่อมแทนการรู้จัก เส้นเชื่อมก็ต้องเป็นเส้นเชื่อมมีทิศทาง เพราะ A รู้จัก B ไม่จำเป็นว่า B ต้องรู้จัก A หรือนั่นก็คือความสัมพันธ์การรู้จักไม่เป็นความสัมพันธ์สมมาตร

                               

โดยทั่วไป^[3] กราฟ G คือคู่อันดับ G = (V, E) โดยที่ V คือเซตของจุดยอด และ E คือเซตของเส้นเชื่อมซึ่งเป็นคู่ไม่อันดับของจุดยอด อันที่จริงนิยามที่กล่าวไปเป็นเพียงประเภทหนึ่งของกราฟที่เรียกว่า กราฟไม่ระบุทิศทาง และเป็นกราฟอย่างง่าย

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

สำหรับประเภทของกราฟต่างๆที่สมบูรณ์มากกว่านี้ โปรดดูข้างล่าง

จุดยอดที่อยู่ที่ปลายของเส้นเชื่อมจะเรียกว่าจุดยอดปลายของเส้นเชื่อม แต่จุดยอดอาจจะไม่เป็นจุดยอดปลายก็ได้ (ในกรณีที่จุดยอดนั้นไม่มีเส้นเชื่อมมาต่อเลย)

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

                                               

กราฟไม่ระบุทิศทาง (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) จะถูกเรียกว่าเป็นเส้นเชื่อมกลับทิศของ 

                                                    

                                                    

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

เราจะกล่าวว่า

-เส้นเชื่อมสองเส้น ประชิด (adjacent) กัน ถ้าเส้นเชื่อมทั้งสองมีจุดปลายร่วมกัน

-จุดยอดสองจุด ประชิด กัน ถ้าจุดยอดทั้งสองเป็นจุดปลายของเส้นเชื่อมเดียวกัน

-เส้นเชื่อม ต่อ (incident) กับจุดปลายของเส้นเชื่อมเสมอ

กราฟที่มีจุดยอดเพียงจุดเดียวและไม่มีเส้นเชื่อมใดๆ เรียกว่า กราฟชัด (trivial graph) กราฟที่มีแต่จุดยอดแต่ไม่มีเส้นเชื่อมใดๆ เรียกว่า กราฟว่าง (empty graph) ส่วนกราฟที่ไม่มีทั้งจุดยอดและเส้นเชื่อม เรียกว่า กราฟศูนย์ (null graph) แต่นิยามนี้ไม่เป็นที่นิยมนัก

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