In the present master thesis a new technique is presented, which when given as input an image with the points of interest noted along with their interconnections, transforms the image in a graph. What follows is the calculation of the Minimun Spanning Tree in that graph. Moreover, an application is presented which utilizes those techniques aiming at the provision of cost-effective solutions that ensure physical access for all groups of visitors and universal access to any mobile services provided. The master thesis as a whole highlights how Graph Theory can contribute in finding efficient solutions to practical problems that relate to the management of cultural sites.
In the sections that follow a review of the literature on the problem of Minimum Spanning Tree is cited and the analysis and design of the corresponding algorithmic framework is presented in detail, which includes the algorithm for automatic transformation of the real image to a graph along with Prim’s algorithm for the calculation of the Minimum Spanning Tree. Moreover, an indicatively complete execution of the application (prototype) is presented, which was implemented for experimental documentation and proof of concept purposes of the proposed algorithms using as input instance the map of the Ancient Agora of Athens. At the end of the master thesis conclusions and suggestions for further improvements are submitted.
(EL)
Στο πλαίσιο της παρούσας διπλωματικής εργασίας, παρουσιάζεται μία νέα τεχνική, η οποία με δεδομένη μια εικόνα με σημειωμένα τα σημεία ενδιαφέροντος και τις διασυνδέσεις τους, τη μεταtρέπει αυτόματα σε γράφημα. Ακολούθως, με χρήση αλγορίθμων από τη βιβλιογραφία, υπολογίζεται το Ελάχιστο Γεννητικό Δέντρο στο γράφημα αυτό. Επιπλέον, παρουσιάζεται εφαρμογή που χρησιμοποιεί αυτές τις τεχνικές με στόχο την παροχή οικονομικά αποδοτικών προτάσεων για εξασφάλιση φυσικής πρόσβασης σε όλες τις πληθυσμιακές ομάδες και καθολική πρόσβαση στις τυχόν παρεχόμενες κινητές υπηρεσίες. Το σύνολο της εργασίας αναδεικνύει το πώς η Θεωρία Γραφημάτων μπορεί να συνεισφέρει στη σύσταση αποδοτικών λύσεων σε πρακτικά προβλήματα που σχετίζονται με την διαχείριση πολιτιστικών χώρων.
Στη συνέχεια, παρατίθεται επισκόπηση της βιβλιογραφίας σχετικά με το πρόβλημα Εύρεσης Ελάχιστου Γεννητικού Δέντρου, παρουσιάζεται λεπτομερώς ο σχεδιασμός και η ανάλυση του σχετικού αλγοριθμικού πλαισίου, που περιλαμβάνει τον αλγόριθμο αυτόματης αναγνώρισης γραφήματος που αντιστοιχεί σε πραγματική εικόνα καθώς και τον αλγόριθμο του Prim για εύρεση ελάχιστου γεννητικού δέντρου. Επιπλέον, παρουσιάζεται αναλυτικά ενδεικτική εκτέλεση της εφαρμογής (prototype) που αναπτύχθηκε για πειραματική τεκμηρίωση και αξιολόγηση (proof of concept) της ορθότητας και ακρίβειας των προτεινόμενων αλγορίθμων για την περίπτωση του χάρτη της Αρχαίας Αγοράς της Αθήνας. Η διπλωματική εργασία ολοκληρώνεται με συμπεράσματα και προτάσεις για μελλοντικές επεκτάσεις.
(EL)
University of Patras
