ทฤษฎีกราฟ - บทนำสั้น ๆ
#1: บทนำสั้นๆ เกี่ยวกับทฤษฎีกราฟ
ความหมายของกราฟ
กราฟเป็นโครงสร้างทางคณิตศาสตร์ที่ประกอบด้วยชุดของจุดยอด (เรียกอีกอย่างว่าโหนด) และชุดของขอบ (เรียกอีกอย่างว่าลิงค์หรือจุดเชื่อมต่อ) ที่เชื่อมต่อจุดยอดคู่หนึ่ง ในกราฟ จุดยอดแสดงถึงวัตถุหรือเอนทิตี และขอบแสดงถึงความสัมพันธ์หรือการโต้ตอบระหว่างกัน
กราฟสามารถแสดงทางคณิตศาสตร์เป็นG = (V,E)โดยที่ V คือเซตของจุดยอด และ E คือเซตของขอบ
ขนาดของกราฟถูกกำหนดเป็นจำนวนของจุดยอดในกราฟ ซึ่งแสดงด้วยและ|V|จำนวนของขอบ ซึ่งแสดงด้วย|E|
ส่วนประกอบของกราฟ
กราฟสามารถแบ่งออกเป็นหลายองค์ประกอบ ได้แก่
- จุดยอด : จุดยอดคือจุดหรือวัตถุในกราฟ จะแสดงเป็นวงกลมหรือจุด
- Edge : ขอบคือเส้นหรือการเชื่อมต่อระหว่างจุดยอดสองจุดในกราฟ มันถูกแสดงเป็นเส้นหรือลูกศรที่เชื่อมต่อวงกลมสองวง
- องศา : องศาของจุดยอดคือจำนวนขอบที่ตกกระทบ กล่าวอีกนัยหนึ่งคือจำนวนขอบที่เชื่อมต่อกับจุดยอด
- เส้นทาง : เส้นทางในกราฟคือลำดับของจุดยอดและขอบที่เชื่อมต่อจุดยอดสองจุด สามารถแสดงเป็นลำดับของจุดยอดและขอบ เช่น(v1, e1, v2, e2, …, vn-1, en-1, vn )
- วัฏจักร: วัฏจักรเป็นเส้นทางในกราฟที่เริ่มต้นและสิ้นสุดที่จุดยอดเดียวกัน สามารถแสดงเป็นลำดับของจุดยอดและขอบ เช่น(v1, e1, v2, e2, …, vn-1, en-1, vn, en, v1 )
กราฟมีหลายประเภท ได้แก่
- กราฟที่ไม่มีทิศทาง : ในกราฟที่ไม่มีทิศทาง ขอบจะไม่มีทิศทาง หมายความว่าสามารถเคลื่อนที่ไปได้ทั้งสองทิศทาง ซึ่งหมายความว่าหากมีขอบระหว่างจุดยอด v1 และจุดยอด v2 ก็จะมีขอบระหว่างจุดยอด v2 และจุดยอด v1
- กราฟกำกับ : ในกราฟกำกับ ขอบจะมีทิศทาง หมายความว่าพวกมันสามารถเคลื่อนที่ไปในทิศทางเดียวเท่านั้น ซึ่งหมายความว่าหากมีขอบจากจุดยอด v1 ถึงจุดยอด v2 ก็จะไม่มีขอบจากจุดยอด v2 ถึงจุดยอด v1
- กราฟถ่วงน้ำหนัก : ในกราฟถ่วงน้ำหนัก แต่ละขอบจะถูกกำหนดน้ำหนักหรือค่าที่แสดงถึงความแข็งแรงหรือต้นทุนของความสัมพันธ์ระหว่างจุดยอด
- กราฟทวิภาคี : ในกราฟทวิภาคี จุดยอดสามารถแบ่งออกเป็นสองชุดที่แยกออกจากกัน เพื่อไม่ให้จุดยอดสองจุดในชุดเดียวกันเชื่อมต่อกันด้วยขอบ ซึ่งหมายความว่ามีเพียงขอบระหว่างจุดยอดในชุดต่างๆ เราจะพูดถึงรายละเอียด นี้ในอนาคต
- กราฟสมบูรณ์ : ในกราฟที่สมบูรณ์ จุดยอดแต่ละจุดเชื่อมต่อกับจุดยอดอื่นๆ ในกราฟ
- กราฟย่อย : กราฟย่อยของกราฟ
Gคือกราฟที่เกิดจากส่วนย่อยของจุดยอดและขอบGของ
ในบทความนี้ เราได้แนะนำแนวคิดพื้นฐานของทฤษฎีกราฟ รวมถึงคำจำกัดความของกราฟ ส่วนประกอบ และประเภทของกราฟ เรากำหนดกราฟเป็นโครงสร้างทางคณิตศาสตร์ที่ประกอบด้วยชุดของจุดยอดและชุดของขอบที่เชื่อมต่อคู่ของจุดยอด เรายังกล่าวถึงส่วนประกอบของกราฟ ได้แก่ จุดยอด ขอบ องศา เส้นทาง และวงรอบ สุดท้าย เราแนะนำกราฟหลายประเภท ได้แก่ กราฟที่ไม่มีทิศทาง กราฟกำกับ กราฟถ่วงน้ำหนัก กราฟสองส่วน กราฟสมบูรณ์ และกราฟย่อย





































![รายการที่เชื่อมโยงคืออะไร? [ส่วนที่ 1]](https://post.nghiatu.com/assets/images/m/max/724/1*Xokk6XOjWyIGCBujkJsCzQ.jpeg)