ทฤษฎีกราฟ - บทนำ

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

กราฟคืออะไร?

กราฟคือการแสดงภาพชุดของวัตถุที่คู่ของวัตถุบางคู่เชื่อมต่อกันด้วยลิงก์ วัตถุที่เชื่อมต่อกันจะแสดงด้วยจุดที่เรียกว่าverticesและลิงก์ที่เชื่อมต่อจุดยอดนั้นเรียกว่า edges.

ปกติกราฟคือคู่ของเซต (V, E), ที่ไหน Vคือเซตของจุดยอดและ E คือเซตของขอบที่เชื่อมคู่ของจุดยอด ดูกราฟต่อไปนี้ -

ในกราฟด้านบน

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

การประยุกต์ใช้ทฤษฎีกราฟ

ทฤษฎีกราฟมีการประยุกต์ใช้ในวิศวกรรมหลากหลายสาขา -

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

Computer Science- ทฤษฎีกราฟใช้สำหรับการศึกษาอัลกอริทึม ตัวอย่างเช่น,

  • อัลกอริทึมของ Kruskal
  • อัลกอริทึมของ Prim
  • อัลกอริทึมของ Dijkstra

Computer Network - ความสัมพันธ์ระหว่างคอมพิวเตอร์ที่เชื่อมต่อกันในเครือข่ายเป็นไปตามหลักการของทฤษฎีกราฟ

Science - โครงสร้างโมเลกุลและโครงสร้างทางเคมีของสารโครงสร้างดีเอ็นเอของสิ่งมีชีวิต ฯลฯ แสดงด้วยกราฟ

Linguistics - โครงสร้างการแยกวิเคราะห์ของภาษาและไวยากรณ์ของภาษาใช้กราฟ

General- เส้นทางระหว่างเมืองสามารถแสดงโดยใช้กราฟ การแสดงข้อมูลที่เรียงลำดับตามลำดับชั้นเช่นแผนผังครอบครัวสามารถใช้เป็นกราฟชนิดพิเศษที่เรียกว่าทรี