Πρωτότυπος Τίτλος:
Υλοποίηση αλγορίθμου απεικόνισης γραφημάτων
Συγγραφέας:
Παπαδάκης, Ηλίας, Χρήστος
Επιβλέπων καθηγητής:
Μιχαήλ, Δημήτριος
Περίληψη:
Τα γραφήματα είναι ένας συνηθισμένος τρόπος απεικόνισης δομών δεδομένων τα οποία χρησιμοποιούν οι υπολογιστές. Η πληροφορία που χειρίζονται πολλά πληροφοριακά συστήματα αναπαρίσταται με δομές γράφου. Για αυτό δημιουργήθηκε η ανάγκη για αλγορίθμους σχεδίασης γράφων.
Σκοπός αυτής της πτυχιακής είναι η υλοποίηση ενός αλγορίθμου απεικόνισης γράφου με βέλτιστο τρόπο που προτάθηκε και σχεδιάστηκε από τους Kamada Tomihisa και Satoru Kawai.
Σε αυτό τον γράφο θεωρούμε ότι οι ακμές που συνδέουν τις κορυφές είναι ελατήρια. Συνεπώς, θεωρούμε σαν βέλτιστο αποτέλεσμα έναν γράφο σε κατάσταση ισορροπίας ,δηλαδή μια κατάσταση που η συνολική δύναμη που ασκείται στο σύστημα από τα ελατήρια να είναι μηδέν.
Θα παρατηρήσουμε στα σχήματα που παρουσιάστουν στα επόμενα κεφάλαια ότι ο αλγόριθμος των Tomihisa Kamada και Satoru Kawai[1] επιτυγχάνει το στόχο του σχεδιάζοντας ευκρινείς γράφους με καλές αποστάσεις μεταξύ των κορυφών και όσο το δυνατόν λιγότερες τέμνουσες ακμές. Ο αλγόριθμος ανταποκρίθηκε πολύ καλά τόσο σε γράφους με λίγες ακμές και κορυφές όσο και πιο σύνθετα σχήματα. Οι δοκιμές αφορούσαν μη κατευθυνόμενους γράφους. Η απόδοση του αλγορίθμου δεν επηρεάζεται από τις αρχικές θέσεις των συντεταγμένων, με αποτέλεσμα να επιτυγχάνει καλή εξισορρόπηση της ενέργειας οποιουδήποτε γράφου κλήθηκε να σχεδιάσει
Σκοπός αυτής της πτυχιακής είναι η υλοποίηση ενός αλγορίθμου απεικόνισης γράφου με βέλτιστο τρόπο που προτάθηκε και σχεδιάστηκε από τους Kamada Tomihisa και Satoru Kawai.
Σε αυτό τον γράφο θεωρούμε ότι οι ακμές που συνδέουν τις κορυφές είναι ελατήρια. Συνεπώς, θεωρούμε σαν βέλτιστο αποτέλεσμα έναν γράφο σε κατάσταση ισορροπίας ,δηλαδή μια κατάσταση που η συνολική δύναμη που ασκείται στο σύστημα από τα ελατήρια να είναι μηδέν.
Θα παρατηρήσουμε στα σχήματα που παρουσιάστουν στα επόμενα κεφάλαια ότι ο αλγόριθμος των Tomihisa Kamada και Satoru Kawai[1] επιτυγχάνει το στόχο του σχεδιάζοντας ευκρινείς γράφους με καλές αποστάσεις μεταξύ των κορυφών και όσο το δυνατόν λιγότερες τέμνουσες ακμές. Ο αλγόριθμος ανταποκρίθηκε πολύ καλά τόσο σε γράφους με λίγες ακμές και κορυφές όσο και πιο σύνθετα σχήματα. Οι δοκιμές αφορούσαν μη κατευθυνόμενους γράφους. Η απόδοση του αλγορίθμου δεν επηρεάζεται από τις αρχικές θέσεις των συντεταγμένων, με αποτέλεσμα να επιτυγχάνει καλή εξισορρόπηση της ενέργειας οποιουδήποτε γράφου κλήθηκε να σχεδιάσει
Ημερομηνία κατάθεσης:
2021-03-23
Γλώσσες Τεκμηρίου:
Ελληνικά
Θεματικές Κατηγορίες:
Ηλεκτρονικοί υπολογιστές. Επιστήμη των υπολογιστών
Λοιπά Θέματα:
Αλγόριθμοι
Λέξεις-κλειδιά:
αλγόριθμος αναπαράστασης γράφου, δύναμη, ενέργεια, γράφοι
Περιγραφή:
39 σ.,εικ.,σχ.
Άδεια χρήσης:
Αναφορά Δημιουργού – Μη Εμπορική Χρήση – Όχι Παράγωγα Έργα 4.0
