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