อภิธานศัพท์ทฤษฎีกราฟ
จากวิกิพีเดีย สารานุกรมเสรี
ทฤษฎีกราฟเติบโตอย่างรวดเร็วในวงการวิจัยด้านคณิตศาสตร์ และมีคำศัพท์เฉพาะทางอยู่หลายคำ บทความนี้จะรวบรวมคำและความหมายของศัพท์ในทฤษฎีกราฟ
สารบัญ |
[แก้] พื้นฐาน
กราฟ G มีส่วนประกอบพื้นฐานอยู่ 2 ส่วนคือ จุดยอด และ เส้นเชื่อม เส้นเชื่อมทุกเส้นมีจุดยอดปลาย 2 จุด ซึ่งจุดยอดปลายจะเชื่อมโยงกัน
จุดยอด มักเขียนแทนด้วยจุด เซตจุดยอดของ G เขียนแทนด้วย V(G) หรือ V อันดับของกราฟ คือ จำนวนของจุดยอด ซึ่งเท่ากับ |V(G)|
เส้นเชื่อม มักเขียนแทนด้วยเส้นที่เชื่อมระหว่างจุดยอด 2 จุด ซึ่งเรียกว่า จุดยอดปลาย เส้นเชื่อมที่มีจุดยอดปลายเป็น x กับ y จะเขียนแทนด้วย xy โดยไม่มีสัญลักษณ์ใดๆอยู่ตรงกลาง เซตของเส้นเชื่อมของ G เขียนแทนด้วย E(G) หรือ E
ขนาดของกราฟ คือจำนวนของเส้นเชื่อม ซึ่งเท่ากับ |E(G)|
วงวน คือ เส้นเชื่อมที่มีจุดยอดปลายเป็นจุดยอดเดียวกัน ลิงก์ คือ เส้นเชื่อมที่มีจุดยอดปลายทั้ง 2 เป็นคนละจุด เส้นเชื่อมซ้ำ คือ เส้นเชื่อมที่มีเส้นเชื่อมอื่นเชื่อมจุดยอดปลายทั้งสองของมันเหมือนกัน เส้นเชื่อมเชิงเดียว คือ เส้นเชื่อมที่ไม่เป็นเส้นเชื่อมซ้ำ กราฟเชิงเดียว คือ กราฟที่ไม่มีเส้นเชื่อมซ้ำและไม่มีวงวน มัลติกราฟ คือ กราฟที่มีเส้นเชื่อมซ้ำแต่มีวงวนหรือไม่มีวงวนก็ได้ กราฟจำลอง คือกราฟที่มีเส้นเชื่อมซ้ำและมีวงวน
การระบุชื่อกราฟ คือ การกำหนดชื่อให้กับเส้นเชื่อมและจุดยอดของกราฟ (โดยทั่วไปมักกำหนดชื่อด้วยจำนวนธรรมชาติ) กราฟที่ระบุชื่อให้กับเส้นเชื่อมหรือจุดยอด จะเรียกว่า กราฟระบุชื่อ ถ้าไม่ได้ระบุชื่อ เรียกว่า กราฟไม่ระบุชื่อ
กราฟศูนย์ คือ กราฟที่ไม่มีจุดยอดและไม่มีเส้นเชื่อมอยู่เลย หรือ เป็นกราฟที่ไม่มีเส้นเชื่อม แต่มีจุดยอดอยู่จำนวนหนึ่ง ในกรณีนี้เราจะเรียกว่า กราฟศูนย์บนจุดยอด n จุด
กราฟอนันต์ คือ กราฟที่มีจุดยอดอยู่เป็นอนันต์ หรือมีเส้นเชื่อมอยู่เป็นอนันต์ กราฟที่ไม่เป็นกราฟอนันต์ เรียกว่า กราฟจำกัด
กราฟ G และ H จะสมสัณฐาน ก็ต่อเมื่อ เราสามารถจับคู่หนึ่งต่อหนึ่งระหว่างจุดยอดของกราฟทั้งสองได้ โดยที่ จุดยอดสองจุดใดๆใน G จะประชิดกันก็ต่อเมื่อ จุดยอดสองจุดที่สมนัยกับมันใน H ประชิดกันด้วย
[แก้] กราฟย่อย
กราฟย่อย ของกราฟ G คือกราฟที่มีเซตจุดยอดและเซตเส้นเชื่อม เป็นเซตย่อยของ G
[แก้] แนวเดิน
แนวเดิน คือ ลำดับสลับระหว่างจุดยอดและเส้นเชื่อม โดยเริ่มต้นและลงท้ายที่จุดยอด โดยที่จุดยอดจะต่อกับเส้นเชื่อมที่อยู่หน้าและตามหลังมันในลำดับ แนวเดินปิดคือแนวเดินที่จุดยอดแรกและจุดยอดท้ายเป็นจุดยอดเดียวกัน แนวเดินที่ไม่เป็นแนวเดินปิดเรียกว่า แนวเดินเปิด
ความยาวของแนวเดิน คือ จำนวนเส้นเชื่อมที่ใช้ในแนวเดิน
รอยเดิน คือ แนวเดินที่ใช้เส้นเชื่อมแต่ละเส้นเพียงครั้งเดียว รอยเดินปิด เรียกว่า ทัวร์ หรือ วงจร
วิถี มักหมายถึง แนวเดินเปิด โดยทั่วไปแล้ว วิถีมักจะหมายถึงวิถีเชิงเดียว นั่นคือ จุดยอดทุกจุดจะติดกับเส้นเชื่อมอย่างมากสองเส้น จากกราฟตัวอย่างข้างบน (5, 2, 1) คือ วิถีที่มีความยาวเท่ากับ 2 วัฏจักร คือ วิถีที่จุดเริ่มต้นกับจุดท้ายเป็นจุดเดียวกัน จากกราฟตัวอย่าง (1, 5, 2, 1) เป็นวัฏจักรที่มีความยาวเท่ากับ 3 วิถีที่มีจุดยอด n จุด เขียนแทนด้วย Pn วัฏจักรที่มีจุดยอด n จุด เขียนแทนด้วย Cn (อย่างไรก็ตาม มีผู้เขียนบางคนใช้ความยาวแทนจำนวนจุดยอด)
วัฏจักรคี่ คือ วัฏจักรที่มีความยาวเป็นจำนวนคี่ วัฏจักรคู่ คือ วัฏจักรที่มีความยาวเป็นจำนวนคู่ มีทฤษฎีบทหนึ่งกล่าวว่า กราฟจะเป็นกราฟสองส่วน ก็ต่อเมื่อ มันไม่มีวัฏจักรคี่อยู่
girthของกราฟ คือ ความยาวของวัฏจักร(เชิงเดียว)ที่สั้นที่สุดในกราฟ เส้นรอบวงของกราฟ คือ ความยาวของวัฏจักร(เชิงเดียว)ที่ยาวที่สุดในกราฟ กราฟที่ไม่มีวัฏจักรจะถือว่ามี girth และเส้นรอบวง เท่ากับอนันต์ ∞
กราฟอวัฏจักร คือ กราฟที่ไม่มีวัฏจักร กราฟวัฏจักรเดียว คือกราฟที่มีวัฏจักรอยู่ 1 วัฏจักร
C1 เรียกว่า วงวน C2 เรียกว่าคู่ของเส้นเชื่อมซ้ำ C3 เรียกว่า รูปสามเหลี่ยม
[แก้] ต้นไม้
ต้นไม้ คือ กราฟเชิงเดียวเชื่อมโยงที่ไม่มีวัฏจักร ใบ คือ จุดยอดที่มีระดับขั้นเท่ากับ 1 เส้นเชื่อมใบ คือ เส้นเชื่อมที่ต่อกับใบ จุดยอดที่ไม่ใช่ใบเรียกว่า จุดยอดภายใน ต้นไม้จะถูกเรียกว่า ต้นไม้มีราก ถ้ามีจุดยอดหนึ่งจุดที่ถูกกำหนดให้เป็นราก ต้นไม้มีรากจะเป็นกราฟอวัฏจักรระบุทิศทางเมื่อเส้นเชื่อมชี้ออกจากรากเสมอ
ต้นไม้ เป็นโครงสร้างข้อมูลที่นิยมใช้กันในวิทยาการคอมพิวเตอร์ (ดูโครงสร้างข้อมูลแบบต้นไม้)
ป่า คือ กลุ่มของต้นไม้ที่ไม่มีจุดยอดร่วมกัน
ต้นไม้ย่อยของกราฟ G คือ กราฟย่อยที่เป็นต้นไม้
ต้นไม้ทอดข้าม คือ กราฟย่อยทอดข้ามที่เป็นต้นไม้ กราฟเชื่อมโยงจะมีต้นไม้ทอดข้ามเสมอ
[แก้] กลุ่มพรรคพวก
กราฟแบบบริบูรณ์ Kn คือ กราฟเชิงเดียวที่มีจุดยอด n จุด และจุดยอดทุกจุดจะประชิดกับจุดยอดอื่นๆทุกจุด กราฟแบบบริบูรณ์ที่มีจุดยอด n จุด เขียนแทนด้วย Kn ซึ่งจะมีเส้นเชื่อม n(n-1)/2 เส้น
กลุ่มพรรคพวกในกราฟ คือ กลุ่มของจุดยอดที่จุดยอดทุกจุดในกลุ่มประชิดกัน กลุ่มพรรคพวกอันดับ k คือ กลุ่มพรรคพวกที่มีจุดยอด k จุด จากตัวอย่างข้างบน จุดยอด 1, 2, 5 เป็นกลุ่มพรรคพวกอันดับ 3 หรือเรียกว่า รูปสามเหลี่ยม
หมายเลขกลุ่มพรรคพวก ω(G) ของกราฟ G คือ อันดับของกลุ่มพรรคพวกที่ใหญ่สุดใน G
[แก้] การประชิด และระดับขั้น
ระดับขั้น dG(v) ของจุดยอด v ในกราฟ G คือ จำนวนเส้นเชื่อมที่ต่อกับ v ถ้าเส้นเชื่อมเป็นวงวนให้นับสองครั้ง จุดเอกเทศ คือ จุดยอดที่มีระดับขั้น 0. ใบ คือ จุดยอดที่มีระดับขั้น 1. จากกราฟตัวอย่าง จุดยอด 1 และ 3 มีระดับขั้น 2. จุดยอด 2, 4, 5 มีระดับขั้น 3. จุดยอด 6 มีระดับขั้น 1. ถ้า E เป็นเซตจำกัดแล้ว ผลบวกของระดับขั้นของจุดยอดในกราฟ จะเท่ากับจำนวนเส้นเชื่อมคูณสอง
ลำดับระดับขั้น คือรายการของระดับขั้นของกราฟ ที่เรียงลำดับจากมากไปน้อย (d1 ≥ d2 ≥ … ≥ dn)
จุดยอด u และจุดยอด v จะประชิดกัน ถ้ามีเส้นเชื่อมเชื่อมระหว่าง u กับ v เขียนแทนด้วย u ↓ v จากกราฟตัวอย่าง จุดยอด 1 กับ 2 ประชิดกัน แต่จุดยอด 2 กับ 4 ไม่ประชิดกัน
ระดับขั้นสูงสุด Δ(G) ของกราฟ G คือระดับขั้นที่มีค่าสูงสุดของจุดยอดในกราฟ ระดับขั้นต่ำสุด δ(G) ของกราฟ G คือระดับขั้นที่มีค่าต่ำสุดของจุดยอดในกราฟ
[แก้] สภาพเชื่อมโยง
[แก้] ดูเพิ่ม
![]() |
อภิธานศัพท์ทฤษฎีกราฟ เป็นบทความเกี่ยวกับ คณิตศาสตร์ ที่ยังไม่สมบูรณ์ ต้องการตรวจสอบ เพิ่มเนื้อหา หรือเพิ่มแหล่งอ้างอิง คุณสามารถช่วยเพิ่มเติมหรือแก้ไข เพื่อให้สมบูรณ์มากขึ้น ข้อมูลเกี่ยวกับ อภิธานศัพท์ทฤษฎีกราฟ ในภาษาอื่น อาจสามารถหาอ่านได้จากเมนู ภาษาอื่น ด้านซ้ายมือ |