Η θεωρία των γραφημάτων είναι μία από τις υποενότητες.τα μαθηματικά, το κύριο χαρακτηριστικό του οποίου είναι η γεωμετρική μέθοδος στη μελέτη των αντικειμένων. Ο ιδρυτής του θεωρείται ο διάσημος μαθηματικός L. Euler.
Εφαρμογή της θεωρίας γραφημάτων μέχρι τα τέλη του 19ου αιώνακατέληξε στην επίλυση προβλημάτων ψυχαγωγίας και δεν προσέλκυσε σημαντική γενική προσοχή. Ξεκινώντας από τον 20ό αιώνα, όταν η θεωρία των γραφημάτων σχηματίστηκε σε μια ανεξάρτητη μαθηματική πειθαρχία, βρήκε ευρεία εφαρμογή σε επιστημονικά πεδία όπως η κυβερνητική, η φυσική, η εφοδιαστική, ο προγραμματισμός, η βιολογία, η ηλεκτρονική, τα συστήματα μεταφορών και επικοινωνιών.
Βασικές έννοιες της θεωρίας γραφημάτων
Η βάση είναι ένα γράφημα.Στην ορολογία, μπορεί κανείς να συναντήσει μια τέτοια ιδέα σαν ένα δίκτυο όμοιο με ένα γράφημα. Ο τελευταίος είναι ένας μη κενός αριθμός σημείων, δηλαδή κορυφές και τμήματα, δηλαδή άκρα, και τα δύο άκρα αντιστοιχούν σε ένα δεδομένο αριθμό σημείων. Η θεωρία των γραφημάτων δεν έχει νόημα στις τιμές των άκρων και των κορυφών. Για παράδειγμα, οι πόλεις και οι δρόμοι που τις συνδέουν, όπου οι πρώτοι είναι οι κορυφές του γραφήματος, και το δεύτερο είναι οι άκρες. Μεγαλύτερη σημασία θεωρητικά δίνεται στα τόξα. Αν μια άκρη έχει μια κατεύθυνση, τότε έχει το όνομα ενός τόξου, εάν ένα γράφημα με προσανατολισμένες άκρες, ονομάζεται digraph.
Στην ορολογία της θεωρίας διακρίνονται επίσης οι ακόλουθες έννοιες:
Μια υπογράμμιση είναι ένα γράφημα του οποίου όλες οι άκρες και οι κορυφές είναι μεταξύ των κορυφών και των άκρων.
Ένα συνδεδεμένο γράφημα είναι ένα με μια αλυσίδα που τις συνδέει για δύο διαφορετικές κορυφές.
Σταθμισμένη συνδεδεμένο γράφημα - αυτό που ρυθμίσετε τη λειτουργία στάθμισης.
Ένα δέντρο είναι ένα συνδεδεμένο γράφημα, χωρίς κύκλους.
Ένας σκελετός είναι μια υπογράμμιση που είναι ένα δέντρο.
Όταν σχεδιάζετε ένα γράφημα σε ένα επίπεδομια συγκεκριμένη σημείωση: η επιλεγμένη κορυφή αντιστοιχεί σε ένα σημείο στην απλούστερη επιφάνεια και εάν υπάρχει μια άκρη μεταξύ των κορυφών, τότε τα αντίστοιχα σημεία συνδέονται με ένα τμήμα. Αν το γράφημα είναι προσανατολισμένο, αυτά τα τμήματα αντικαθίστανται από βέλη.
Αλλά μην συγκρίνετε την εικόνα του γραφήματος με αυτόαπό τους εαυτούς μας, δηλ. με μια αφηρημένη δομή, επειδή μπορούν να δοθούν περισσότερες από μία γραφικές παραστάσεις σε ένα γράφημα. Το σχέδιο στο επίπεδο δίνονται για να δούμε ποια ζεύγη κορυφών συνδέονται με άκρα και που δεν είναι.
Μεταξύ ορισμένων προβλημάτων της θεωρίας γραφημάτων, υπάρχουν:
- Το έργο της πιο σύντομης αλυσίδας (αντικατάσταση εξοπλισμού, τοποθέτηση ασθενοφόρων και τηλεφωνικά κέντρα).
- Το πρόβλημα της μέγιστης ροής (εξορθολογισμός της κυκλοφορίας σε ένα δυναμικό δίκτυο, διανομή εργασίας, οργάνωση εύρους ζώνης).
- Το πρόβλημα των επιστρώσεων και της συσκευασίας (τοποθέτηση κέντρων ελέγχου).
- Χρωματισμός σε γραφήματα (κατανομή μνήμης σε ηλεκτρονικούς υπολογιστές).
- Δίκτυα επικοινωνίας και γραφήματα (δημιουργία δικτύου επικοινωνίας, ανάλυση δικτύων επικοινωνίας).
Επί του παρόντος, είναι αδύνατο να προγραμματιστούν οι περισσότερες εργασίες χωρίς γνώση της θεωρίας γραφημάτων. Αυτό διευκολύνει και απλοποιεί τη δουλειά με τους υπολογιστές.
Ο προγραμματισμός χρησιμοποιεί πολλές δομές καικαθολικές μέθοδοι για την επίλυση προβλημάτων, και μία από αυτές είναι η θεωρία γραφημάτων. Η αξία του είναι δύσκολο να υπερεκτιμηθεί. Η θεωρία γραφημάτων στον προγραμματισμό διευκολύνει την εύρεση πληροφοριών, τη βελτιστοποίηση προγραμμάτων, τη μετατροπή και τη διανομή δεδομένων. Χάρη στους αλγορίθμους της θεωρίας γίνεται δυνατή η χρήση και η αξιολόγησή τους για την επίλυση συγκεκριμένων προβλημάτων, η τροποποίηση του αλγόριθμου χωρίς μείωση του βαθμού μαθηματικής αξιοπιστίας της τελικής έκδοσης του προγράμματος.
Μια σημαντική ιδιότητα ενός συστήματος ή ενός μοντέλου ελέγχουείναι ένα σύνολο δυαδικών σχέσεων σε ένα σύνολο ενεργειών και μονάδων δεδομένων. Αυτές οι δομές είναι τα μόνα μέρη των προγραμμάτων και οι πληροφορίες που μετασχηματίζουν. Επομένως, τα γραφήματα αποτελούν τη βάση της κατασκευής του προγραμματιστή.
