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

บทความนี้เกี่ยวกับกราฟที่ประกอบไปด้วยจุดยอดและเส้นเชื่อม สำหรับกราฟของฟังก์ชันทางคณิตศาสตร์ ดูที่ กราฟของฟังก์ชัน สำหรับความหมายอื่น ดูที่ กราฟ (แก้ความกำกวม)

ข้อมูลเพิ่มเติม: ทฤษฎีกราฟ

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

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

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

จุดยอดอาจจะถูกเรียกว่าโหนด ปม หรือจุด ในขณะที่เส้นเชื่อมอาจถูกเรียกว่าเส้น คำว่า "กราฟ" ถูกใช้ครั้งแรกโดย J.J. Sylvester ในปี พ.ศ. 2421

นิยาม

ตัวอย่างทั่วไปของกราฟ (อันที่จริงคือกราฟเทียม) ซึ่งมี 3 จุดยอดและ 6 เส้นเชื่อม

โดยทั่วไป กราฟ 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) ซึ่งไม่มีน้ำหนักถ่วงที่เส้นเชื่อม

คุณลักษณะของกราฟ

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

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

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

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

ตัวอย่าง

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

จากรูปทางขวา เขียนเป็นกราฟได้ดังนี้

• 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)
• กราฟอวัฏจักรระบุทิศทาง (Directed acyclic graph)

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

ในไฮเปอร์กราฟ เส้นเชื่อมสามารถเชื่อมได้มากกว่าสองจุด

ทุก ๆ กราฟ ก่อให้เกิด เมทรอยด์ แต่โดยทั่วไปแล้ว เราจะไม่สามารถสร้างกราฟกลับมาจากเมทรอยด์ของมันได้ ดังนั้นเมทรอยด์จึงไม่ใช่นัยทั่วไปของกราฟ

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

ดูเพิ่ม

• อภิธานศัพท์ทฤษฎีกราฟ