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

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

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

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

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

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

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

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

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

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

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

เส้นเชื่อม {*u*, *v*} อาจเขียนให้สั้นว่า *uv* ก็ได้

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

#### กราฟระบุทิศทาง
125px|thumb|left|กราฟระบุทิศทาง

**กราฟระบุทิศทาง** (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)

## ตัวอย่าง
thumb|250px|right|กราฟที่มีจุดยอด 6 จุด และเส้นเชื่อม 7 เส้น
จากรูปทางขวา เขียนเป็นกราฟได้ดังนี้
* *V* = {1,2,3,4,5,6}
* *E* = 

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

## กราฟที่สำคัญ
* กราฟบริบูรณ์ (complete graph) คือ กราฟที่ทุก ๆ คู่ของจุดยอดจะถูกเชื่อมด้วยเส้นเชื่อม ดังนั้น กราฟนี้จะมีเส้นเชื่อมทุกเส้นที่เป็นไปได้
* กราฟเชิงระนาบ (planar graph) คือ กราฟที่สามารถเขียนบนระนาบได้ โดยไม่มีเส้นเชื่อมใดๆตัดกัน
* ต้นไม้ (tree) คือ กราฟเชื่อมโยงที่ไม่มีวัฏจักร
* กราฟสองส่วน (bipartite graph)
* กราฟสมบูรณ์ (Perfect graph)
* กราฟเส้น (Line graph)
* โคกราฟ (Cograph)
* กราฟอวัฏจักรระบุทิศทาง (Directed acyclic graph)

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

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

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

## อ้างอิง

## ดูเพิ่ม
* อภิธานศัพท์ทฤษฎีกราฟ

ทฤษฎีกราฟ
หมวดหมู่:วัตถุทฤษฎีกราฟ