ทฤษฎีกราฟ — จุดยอด เส้นเชื่อม และแนวคิดพื้นฐาน

ทฤษฎีกราฟคือการศึกษา กราฟ ซึ่งเป็นโครงสร้างที่ประกอบด้วย จุดยอด และ เส้นเชื่อม จุดยอดคือวัตถุหนึ่ง ๆ และเส้นเชื่อมแสดงความสัมพันธ์ระหว่างวัตถุสองชิ้น

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

กราฟในคณิตศาสตร์หมายถึงอะไร

ใน กราฟไม่มีทิศทาง เส้นเชื่อมบอกว่าจุดยอดสองจุดเชื่อมต่อกัน และการเชื่อมต่อนั้นไม่มีทิศทาง ถ้า $A$ เชื่อมกับ $B$ ก็แปลว่า $B$ เชื่อมกับ $A$ ด้วย

ใน กราฟมีทิศทาง เส้นเชื่อมมีทิศทาง ดังนั้น $A \to B$ และ $B \to A$ จึงเป็นคนละข้อความ ตัวอย่างสำหรับผู้เริ่มต้นจำนวนมากใช้ กราฟไม่มีทิศทางแบบอย่างง่าย ซึ่งหมายถึงไม่มีลูป และไม่มีเส้นเชื่อมซ้ำระหว่างจุดยอดคู่เดิม

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

คำศัพท์พื้นฐานของทฤษฎีกราฟที่ควรรู้ก่อน

จุดยอดและเส้นเชื่อม

จุดยอดคือสิ่งที่คุณต้องการติดตาม เส้นเชื่อมคือความสัมพันธ์ที่คุณต้องการติดตาม

ถ้ากราฟใช้แทนเมืองและถนน เมืองคือจุดยอด และถนนคือเส้นเชื่อม

ดีกรี

ในกราฟไม่มีทิศทาง ดีกรี ของจุดยอดคือจำนวนเส้นเชื่อมที่แตะจุดยอดนั้น

ถ้าเมืองหนึ่งมีถนนเชื่อมไปยังอีกสามเมือง ดีกรีของมันคือ $3$

เส้นทาง

เส้นทาง คือ ลำดับของจุดยอดที่แต่ละคู่ที่อยู่ติดกันเชื่อมกันด้วยเส้นเชื่อม

ถ้ามีเส้นทางจากจุดยอดหนึ่งไปยังอีกจุดยอดหนึ่ง คุณก็สามารถเดินทางจากจุดหนึ่งไปอีกจุดหนึ่งได้โดยตามเส้นเชื่อมไป

วงจร

วงจร คือเส้นทางที่เริ่มต้นและสิ้นสุดที่จุดยอดเดียวกัน ตามนิยามพื้นฐานทั่วไป จะไม่มีจุดยอดอื่นถูกใช้ซ้ำ

วงจรแสดงให้เห็นว่ามีลูปปิดอยู่ในกราฟ

กราฟเชื่อมต่อและองค์ประกอบเชื่อมต่อ

กราฟไม่มีทิศทางเป็น กราฟเชื่อมต่อ ถ้าสามารถไปถึงทุกจุดยอดจากทุกจุดยอดอื่นได้ด้วยเส้นทางบางเส้น

ถ้าไม่เป็นเช่นนั้น กราฟจะแยกออกเป็น องค์ประกอบเชื่อมต่อ แต่ละองค์ประกอบคือส่วนของกราฟที่เชื่อมต่อกันภายในตัวเอง

ตัวอย่างแบบทำไปพร้อมกัน: กราฟเล็กหนึ่งกราฟ

สมมติว่ากราฟมีจุดยอด $A$, $B$, $C$, $D$ และ $E$ โดยมีเส้นเชื่อม

$$AB,\ AC,\ BC,\ CD$$

กราฟนี้ให้รูปสามเหลี่ยมบน $A$, $B$ และ $C$ มีเส้นเชื่อมเพิ่มอีกหนึ่งเส้นจาก $C$ ไป $D$ และมีจุดยอดโดดเดี่ยวคือ $E$

ตอนนี้แนวคิดหลักต่าง ๆ จะเห็นได้ง่าย

ดีกรีมีค่าเป็น

$$\deg(A)=2,\ \deg(B)=2,\ \deg(C)=3,\ \deg(D)=1,\ \deg(E)=0$$

มีเส้นทางจาก $A$ ไป $D$ คือ

$$A-C-D$$

มีวงจรคือ

$$A-B-C-A$$

กราฟนี้ ไม่เชื่อมต่อ เพราะไม่สามารถไปถึง $E$ จากจุดยอดอื่นได้ ดังนั้นกราฟนี้จึงมีองค์ประกอบเชื่อมต่อสองส่วน: ส่วนหนึ่งมี $A,B,C,D$ และอีกส่วนหนึ่งมีเพียง $E$

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

ตรวจเร็ว ๆ: ผลรวมของดีกรี

สำหรับกราฟไม่มีทิศทางจำกัดใด ๆ

$$\sum \deg(v) = 2|E|$$

สิ่งนี้เป็นจริงเพราะเส้นเชื่อมทุกเส้นแตะปลายอยู่พอดีสองด้าน ดังนั้นแต่ละเส้นเชื่อมจึงเพิ่มค่า $1$ ให้กับการนับดีกรีสองครั้ง

ในตัวอย่างข้างบน ผลรวมดีกรีคือ

$$2+2+3+1+0=8$$

และจำนวนเส้นเชื่อมคือ $4$ ดังนั้น

$$2|E| = 2 \cdot 4 = 8$$

นี่เป็นวิธีตรวจสอบที่มีประโยชน์เมื่อคุณนับดีกรีด้วยมือ ถ้าตัวเลขไม่ตรงกัน แสดงว่ามีบางอย่างผิดพลาด

ข้อผิดพลาดที่พบบ่อยในทฤษฎีกราฟ

สับสนระหว่างจุดยอดกับเส้นเชื่อม

จุดยอดคือวัตถุ เส้นเชื่อมคือความสัมพันธ์ระหว่างวัตถุเหล่านั้น

ลืมว่ากำลังใช้กราฟชนิดใด

ข้อความที่เป็นจริงสำหรับกราฟไม่มีทิศทางแบบอย่างง่าย อาจต้องปรับเมื่อเปลี่ยนเป็นกราฟมีทิศทาง หรือกราฟที่อนุญาตให้มีลูป

มองเส้นทางเหมือนเป็นวงจร

เส้นทางไม่จำเป็นต้องกลับมาที่จุดเริ่มต้น แต่วงจรต้องกลับมา

มองข้ามจุดยอดโดดเดี่ยว

จุดยอดที่มีดีกรี $0$ ยังถือเป็นส่วนหนึ่งของกราฟ และอาจเปลี่ยนได้ว่ากราฟเชื่อมต่อหรือไม่

พื้นฐานทฤษฎีกราฟถูกใช้ที่ไหนบ้าง

แนวคิดเหล่านี้ปรากฏในเครือข่ายคอมพิวเตอร์ การวางแผนเส้นทาง การจัดตาราง ระบบแนะนำ และเครือข่ายสังคม บริบทอาจเปลี่ยนไป แต่คำถามเดิมยังคงเกิดขึ้นเสมอ: อะไรเชื่อมต่อกัน อะไรไปถึงกันได้ และลูปอยู่ตรงไหน

นั่นจึงเป็นเหตุผลที่ทฤษฎีกราฟปรากฏตั้งแต่ช่วงต้นทั้งในวิชาคณิตศาสตร์ไม่ต่อเนื่องและวิทยาการคอมพิวเตอร์

ลองทำกับกราฟที่คล้ายกัน

วาดจุดยอดสี่จุด $P$, $Q$, $R$ และ $S$ แล้วเพิ่มเส้นเชื่อม $PQ$, $QR$, $RS$ และ $SP$

จากนั้นตอบสามคำถาม: ดีกรีของแต่ละจุดยอดคือเท่าไร กราฟเชื่อมต่อหรือไม่ และกราฟมีวงจรหรือไม่