ทฤษฎีกราฟ - บทนำสั้น ๆ

Mar 15 2023
#1: บทนำสั้นๆ เกี่ยวกับทฤษฎีกราฟ คำจำกัดความของกราฟ กราฟคือโครงสร้างทางคณิตศาสตร์ที่ประกอบด้วยชุดของจุดยอด (หรือที่เรียกว่าโหนด) และชุดของขอบ (หรือที่เรียกว่าลิงก์หรือจุดเชื่อมต่อ) ที่เชื่อมต่อจุดยอดคู่หนึ่ง ในกราฟ จุดยอดแสดงถึงวัตถุหรือเอนทิตี และขอบแสดงถึงความสัมพันธ์หรือการโต้ตอบระหว่างกัน

#1: บทนำสั้นๆ เกี่ยวกับทฤษฎีกราฟ

สร้างโดย AI Art — Hotpot.ai (ทฤษฎีกราฟ)

ความหมายของกราฟ

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

กราฟสามารถแสดงทางคณิตศาสตร์เป็น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 ถึง V4)

กราฟมีหลายประเภท ได้แก่

  • กราฟที่ไม่มีทิศทาง : ในกราฟที่ไม่มีทิศทาง ขอบจะไม่มีทิศทาง หมายความว่าสามารถเคลื่อนที่ไปได้ทั้งสองทิศทาง ซึ่งหมายความว่าหากมีขอบระหว่างจุดยอด v1 และจุดยอด v2 ก็จะมีขอบระหว่างจุดยอด v2 และจุดยอด v1
  • กราฟกำกับ : ในกราฟกำกับ ขอบจะมีทิศทาง หมายความว่าพวกมันสามารถเคลื่อนที่ไปในทิศทางเดียวเท่านั้น ซึ่งหมายความว่าหากมีขอบจากจุดยอด v1 ถึงจุดยอด v2 ก็จะไม่มีขอบจากจุดยอด v2 ถึงจุดยอด v1
  • รูปภาพโดยผู้เขียน (กำกับกราฟ)
  • กราฟถ่วงน้ำหนัก : ในกราฟถ่วงน้ำหนัก แต่ละขอบจะถูกกำหนดน้ำหนักหรือค่าที่แสดงถึงความแข็งแรงหรือต้นทุนของความสัมพันธ์ระหว่างจุดยอด
  • กราฟทวิภาคี : ในกราฟทวิภาคี จุดยอดสามารถแบ่งออกเป็นสองชุดที่แยกออกจากกัน เพื่อไม่ให้จุดยอดสองจุดในชุดเดียวกันเชื่อมต่อกันด้วยขอบ ซึ่งหมายความว่ามีเพียงขอบระหว่างจุดยอดในชุดต่างๆ เราจะพูดถึงรายละเอียด นี้ในอนาคต
  • รูปภาพโดยผู้เขียน (กราฟสองฝ่าย)
  • กราฟสมบูรณ์ : ในกราฟที่สมบูรณ์ จุดยอดแต่ละจุดเชื่อมต่อกับจุดยอดอื่นๆ ในกราฟ
  • กราฟย่อย : กราฟย่อยของกราฟGคือกราฟที่เกิดจากส่วนย่อยของจุดยอดและขอบGของ

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