ทฤษฎีกราฟ

ทฤษฎีกราฟเป็นส่วนย่อยของคณิตศาสตร์ซึ่งลักษณะเด่นหลักของการคำนวณคือวิธีทางเรขาคณิตในการศึกษาวัตถุ ผู้ก่อตั้งได้รับการยกย่องว่าเป็น นักคณิตศาสตร์ชื่อดังอย่าง L. Euler

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

แนวคิดพื้นฐานของทฤษฎีกราฟ

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

ในคำศัพท์ของทฤษฎีแนวคิดต่อไปนี้ยังโดดเด่น:

กราฟย่อยคือกราฟขอบและจุดยอดทั้งหมดซึ่งอยู่ระหว่างจุดยอดและขอบ

กราฟที่เชื่อมต่อคือกราฟที่เชื่อมต่อกันเป็นจุด ๆ สองจุด

กราฟที่มีการถ่วงน้ำหนักคือกราฟที่มีฟังก์ชันน้ำหนัก

ต้นไม้เป็นกราฟที่เชื่อมต่อโดยไม่มีรอบ

โครงกระดูกเป็น subgraph ที่เป็นต้นไม้

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

แต่อย่าเปรียบเทียบภาพของกราฟกับโครงสร้างนั่นคือมีโครงสร้างนามธรรมเนื่องจากกราฟหนึ่งสามารถให้การแสดงผลแบบกราฟิกได้มากกว่าหนึ่งภาพ การวาดภาพบนระนาบจะได้รับเพื่อดูว่าจุดยอดของจุดใดมีการรวมกันตามขอบและที่ไม่ได้

ในบรรดาปัญหาของทฤษฎีกราฟมี:

1. งานของห่วงโซ่ที่สั้นที่สุด (เปลี่ยนอุปกรณ์จัดตำแหน่งของสถานีรถพยาบาลและสถานีโทรศัพท์)
2. ปัญหาของการไหลสูงสุด (การสั่งซื้อของการจราจรในเครือข่ายแบบไดนามิกการกระจายงานการจัดองค์กรของความจุ)
3. งานของการเคลือบและบรรจุภัณฑ์ (ตำแหน่งของจุดส่ง)
4. ระบายสีในกราฟ (ตำแหน่งของหน่วยความจำในคอมพิวเตอร์อิเล็กทรอนิกส์)
5. การสื่อสารของเครือข่ายและกราฟ (การสร้างเครือข่ายการสื่อสารการวิเคราะห์เครือข่ายการสื่อสาร)

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

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

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