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

ทฤษฎีกราฟเติบโตอย่างรวดเร็วในวงการวิจัยด้านคณิตศาสตร์ และมีคำศัพท์เฉพาะทางอยู่หลายคำ บทความนี้จะรวบรวมคำและความหมายของศัพท์ในทฤษฎีกราฟ

## พื้นฐาน

**กราฟ** *G* มีส่วนประกอบพื้นฐานอยู่ 2 ส่วนคือ *จุดยอด* และ *เส้นเชื่อม* เส้นเชื่อมทุกเส้นมี **จุดยอดปลาย** 2 จุด ซึ่งจุดยอดปลายจะ **เชื่อมโยง** หรือ **ประชิด** กัน ดังนั้นจึงสามารถนิยามเส้นเชื่อมในรูปแบบของคู่ไม่อันดับในกรณีของกราฟไม่มีทิศทาง หรือคู่อันดับในกรณีของกราฟมีทิศทาง (อ่านหัวข้อทิศทาง)

**[[จุดยอด (ทฤษฎีกราฟ)|จุดยอด]]** มักเขียนแทนด้วย *จุด* **เซตจุดยอด** ของ *G* เขียนแทนด้วย *V(G)* หรือ *V* **อันดับ** ของกราฟ คือ จำนวนของจุดยอด ซึ่งเท่ากับ |*V(G)*|

**เส้นเชื่อม** (ในที่นี้คือเส้นเชื่อมไม่มีทิศทางซึ่งเป็นคู่ไม่อันดับของจุดยอด) มักเขียนแทนด้วย *เส้น* ที่เชื่อมระหว่างจุดยอด (**จุดยอดปลาย**) 2 จุด เส้นเชื่อมที่มีจุดยอดปลายเป็น *x* กับ *y* จะเขียนแทนด้วย *xy* โดยไม่มีสัญลักษณ์ใดๆอยู่ตรงกลาง
เซตของเส้นเชื่อมของ *G* เขียนแทนด้วย *E* (*G*) หรือ *E*

**ขนาด** ของกราฟ คือจำนวนของเส้นเชื่อม ซึ่งเท่ากับ |*E(G)*|

**[[วงวน]]** คือ เส้นเชื่อมที่มีจุดยอดปลายเป็นจุดยอดเดียวกัน **ลิงก์** คือ เส้นเชื่อมที่มีจุดยอดปลายทั้ง 2 เป็นคนละจุด **เส้นเชื่อมซ้ำ** คือ เส้นเชื่อมที่มีเส้นเชื่อมอื่นเชื่อมจุดยอดปลายทั้งสองของมันเหมือนกัน **เส้นเชื่อมเชิงเดียว** คือ เส้นเชื่อมที่ไม่เป็นเส้นเชื่อมซ้ำ **กราฟเชิงเดียว** คือ กราฟที่ไม่มีเส้นเชื่อมซ้ำและไม่มีวงวน **[[มัลติกราฟ]]** คือ กราฟที่อาจมีเส้นเชื่อมซ้ำแต่นิยามอนุญาตให้มีวงวนหรือไม่มีวงวนก็ได้ **[[กราฟเทียม]]** คือกราฟที่อาจมีเส้นเชื่อมซ้ำและอาจมีวงวน

**การระบุชื่อกราฟ** คือ การกำหนดชื่อให้กับเส้นเชื่อมและจุดยอดของกราฟ (โดยทั่วไปมักกำหนดชื่อด้วยจำนวนธรรมชาติ) กราฟที่ระบุชื่อให้กับเส้นเชื่อมหรือจุดยอด จะเรียกว่า **[[กราฟระบุชื่อ]]** ถ้าไม่ได้ระบุชื่อ เรียกว่า **กราฟไม่ระบุชื่อ** อาจจำแนกเป็นการระบุชื่อที่จุดยอดหรือเส้นเชื่อมอีกก็ได้

frame|กราฟเชิงเดียวระบุชื่อ ที่มีเซตจุดยอด ''V'' = {1, 2, 3, 4, 5, 6} และเซตเส้นเชื่อม ''E'' =

**กราฟศูนย์** คือ กราฟที่ไม่มีจุดยอดและไม่มีเส้นเชื่อมอยู่เลย หรือ เป็นกราฟที่ไม่มีเส้นเชื่อม แต่มีจุดยอดอยู่จำนวนหนึ่ง ในกรณีนี้เราจะเรียกว่า **กราฟศูนย์บนจุดยอด ''n'' จุด**

**กราฟอนันต์** คือ กราฟที่มีจุดยอดอยู่เป็นอนันต์ หรือมีเส้นเชื่อมอยู่เป็นอนันต์ กราฟที่ไม่เป็นกราฟอนันต์ เรียกว่า **กราฟจำกัด**

กราฟ *G* และ *H* จะ **สมสัณฐาน** ก็ต่อเมื่อ เราสามารถจับคู่หนึ่งต่อหนึ่งระหว่างจุดยอดของกราฟทั้งสองได้ โดยที่ จุดยอดสองจุดใด ๆ ใน *G* จะประชิดกันก็ต่อเมื่อ จุดยอดสองจุดที่สมนัยกับมันใน *H* ประชิดกันด้วย

### กราฟย่อย

**กราฟย่อย** ของกราฟ *G* คือกราฟที่มีเซตจุดยอดและเซตเส้นเชื่อม เป็นเซตย่อยของ *G*

### แนวเดิน

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

**ความยาว** ของแนวเดิน คือ จำนวนเส้นเชื่อมที่ใช้ในแนวเดิน

**รอยเดิน** คือ แนวเดินที่ใช้เส้นเชื่อมแต่ละเส้นเพียงครั้งเดียว รอยเดินปิด เรียกว่า **ทัวร์** หรือ **วงจร**

**[[วิถี (ทฤษฎีกราฟ)|วิถี]]** มักหมายถึง *แนวเดินเปิด* โดยทั่วไปแล้ว วิถีมักจะหมายถึงวิถีเชิงเดียว นั่นคือ จุดยอดทุกจุดจะติดกับเส้นเชื่อมอย่างมากสองเส้น จากกราฟตัวอย่างข้างบน (5, 2, 1) คือ วิถีที่มีความยาวเท่ากับ 2 **วัฏจักร** คือ วิถีที่จุดเริ่มต้นกับจุดท้ายเป็นจุดเดียวกัน จากกราฟตัวอย่าง (1, 5, 2, 1) เป็นวัฏจักรที่มีความยาวเท่ากับ 3 วิถีที่มีจุดยอด *n* จุด เขียนแทนด้วย *P<sub>n</sub>* วัฏจักรที่มีจุดยอด *n* จุด เขียนแทนด้วย *C<sub>n</sub>* (อย่างไรก็ตาม มีผู้เขียนบางคนใช้ความยาวแทนจำนวนจุดยอด)

**วัฏจักรคี่** คือ วัฏจักรที่มีความยาวเป็นจำนวนคี่ **วัฏจักรคู่** คือ วัฏจักรที่มีความยาวเป็นจำนวนคู่ มีทฤษฎีบทหนึ่งกล่าวว่า กราฟจะเป็นกราฟสองส่วน ก็ต่อเมื่อ มันไม่มีวัฏจักรคี่อยู่

**[[girth]]** ของกราฟ คือ ความยาวของวัฏจักร (เชิงเดียว) ที่สั้นที่สุดในกราฟ **เส้นรอบวง** ของกราฟ คือ ความยาวของวัฏจักร (เชิงเดียว) ที่ยาวที่สุดในกราฟ กราฟที่ไม่มีวัฏจักรจะถือว่ามี girth และเส้นรอบวง เท่ากับอนันต์ ∞

**กราฟอวัฏจักร** คือ กราฟที่ไม่มีวัฏจักร **[[กราฟวัฏจักรเดียว]]** คือกราฟที่มีวัฏจักรอยู่ 1 วัฏจักร

*C*1 เรียกว่า **วงวน** *C*2 เรียกว่าคู่ของ**เส้นเชื่อมซ้ำ** *C*3 เรียกว่า **รูปสามเหลี่ยม**

### ต้นไม้

**[[ต้นไม้ (ทฤษฎีกราฟ)|ต้นไม้]]** คือ กราฟเชิงเดียวเชื่อมโยงที่ไม่มีวัฏจักร **ใบ** คือ จุดยอดที่มีระดับขั้นเท่ากับ 1 **เส้นเชื่อมใบ** คือ เส้นเชื่อมที่ต่อกับใบ จุดยอดที่ไม่ใช่ใบเรียกว่า **จุดยอดภายใน** ต้นไม้จะถูกเรียกว่า **ต้นไม้มีราก** ถ้ามีจุดยอดหนึ่งจุดที่ถูกกำหนดให้เป็น **ราก** ต้นไม้มีรากจะเป็น**[[กราฟอวัฏจักรระบุทิศทาง]]**เมื่อเส้นเชื่อมชี้ออกจากรากเสมอ

ต้นไม้ เป็นโครงสร้างข้อมูลที่นิยมใช้กันในวิทยาการคอมพิวเตอร์ (ดูโครงสร้างข้อมูลแบบต้นไม้)

**ป่า** คือ กลุ่มของต้นไม้ที่ไม่มีจุดยอดร่วมกัน

**ต้นไม้ย่อย** ของกราฟ *G* คือ กราฟย่อยที่เป็นต้นไม้

**[[ต้นไม้ทอดข้าม]]** คือ กราฟย่อยทอดข้ามที่เป็นต้นไม้ กราฟเชื่อมโยงจะมีต้นไม้ทอดข้ามเสมอ

### กลุ่มพรรคพวก

**[[กราฟแบบบริบูรณ์]]** *K<sub>n</sub>* คือ กราฟเชิงเดียวที่มีจุดยอด *n* จุด และจุดยอดทุกจุดจะประชิดกับจุดยอดอื่น ๆ ทุกจุด กราฟแบบบริบูรณ์ที่มีจุดยอด *n* จุด เขียนแทนด้วย *K<sub>n</sub>* ซึ่งจะมีเส้นเชื่อม *n* (*n*-1)/2 เส้น

**[[กลุ่มพรรคพวก]]** ในกราฟ คือ กลุ่มของจุดยอดที่จุดยอดทุกจุดในกลุ่มประชิดกัน **กลุ่มพรรคพวกอันดับ ''k*** คือ กลุ่มพรรคพวกที่มีจุดยอด *k* จุด จากตัวอย่างข้างบน จุดยอด 1, 2, 5 เป็นกลุ่มพรรคพวกอันดับ 3 หรือเรียกว่า *รูปสามเหลี่ยม*

*'หมายเลขกลุ่มพรรคพวก** ω (''G'') ของกราฟ ''G'' คือ อันดับของกลุ่มพรรคพวกที่ใหญ่สุดใน ''G''

=== ส่วนประกอบที่เชื่อมกันแบบเข้ม ===


== การประชิด และระดับขั้น ==
**ระดับขั้น** ''d<sub>G</sub>'' (''v'') ของจุดยอด ''v'' ในกราฟ ''G'' คือ จำนวนเส้นเชื่อมที่ต่อกับ ''v'' ถ้าเส้นเชื่อมเป็นวงวนให้นับสองครั้ง จุดเอกเทศ คือ จุดยอดที่มีระดับขั้น 0. ใบ คือ จุดยอดที่มีระดับขั้น 1. จากกราฟตัวอย่าง จุดยอด 1 และ 3 มีระดับขั้น 2. จุดยอด 2, 4, 5 มีระดับขั้น 3. จุดยอด 6 มีระดับขั้น 1. ถ้า ''E'' เป็นเซตจำกัดแล้ว ผลบวกของระดับขั้นของจุดยอดในกราฟ จะเท่ากับจำนวนเส้นเชื่อมคูณสอง

**ลำดับระดับขั้น** คือรายการของระดับขั้นของกราฟ ที่เรียงลำดับจากมากไปน้อย (''d''<sub>1</sub> ≥ ''d''<sub>2</sub> ≥ … ≥ ''d<sub>n</sub>'')

จุดยอด ''u'' และจุดยอด ''v'' จะ**ประชิด**กัน ถ้ามีเส้นเชื่อมเชื่อมระหว่าง ''u'' กับ ''v'' เขียนแทนด้วย ''u'' ↓ ''v'' จากกราฟตัวอย่าง จุดยอด 1 กับ 2 ประชิดกัน แต่จุดยอด 2 กับ 4 ไม่ประชิดกัน

**ระดับขั้นสูงสุด** Δ (''G'') ของกราฟ ''G'' คือระดับขั้นที่มีค่าสูงสุดของจุดยอดในกราฟ **ระดับขั้นต่ำสุด** δ (''G'') ของกราฟ ''G'' คือระดับขั้นที่มีค่าต่ำสุดของจุดยอดในกราฟ

== ความต่อเนื่อง ==


== ระยะทาง ==


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

โดยทั่วไปหากกล่าวถึงกราฟจะหมายถึง **กราฟไม่ถ่วงน้ำหนัก''' (unweighted graph) ซึ่งไม่มีน้ำหนักถ่วงที่เส้นเชื่อม

## ทิศทาง

### กราฟอวัฏจักรระบุทิศทาง

## การให้สีกราฟ

## อื่น ๆ
* ไฮเปอร์กราฟ (:en:hypergraph)
* กราฟสองส่วน
* กราฟสองส่วนบริบูรณ์
* กราฟออยเลอร์ (:en:Eulerian path)
* กราฟแฮมิลตัน (:en:Hamiltonian path)
* เซตอิสระ
* การจับคู่ (:en:Matching (graph theory))
* สะพาน (ทฤษฎีกราฟ) (:en:Bridge (graph theory))
* ระยะทาง (:en:Distance (graph theory))
* กราฟเชิงระนาบ
* ปัญหาวิถีสั้นสุด
* ต้นไม้ทอดข้ามที่น้อยที่สุด
* การไหลมากที่สุด (:en:Maximum flow)
* ตัวยืนยงของกราฟ (:en:graph invariant)

## ดูเพิ่ม
* กราฟ (คณิตศาสตร์)
* ทฤษฎีกราฟ

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