Εμφάνιση απλής εγγραφής

dc.contributor.advisorΒλάχος, Δημήτριος
dc.contributor.authorΣελίμης, Δημήτριος
dc.date.accessioned2013-11-19T10:48:33Z
dc.date.available2013-11-19T10:48:33Z
dc.date.issued2013
dc.identifier.urihttp://amitos.library.uop.gr/xmlui/handle/123456789/981
dc.descriptionΜ.Δ.Ε. 34el
dc.description.abstract1 Εισαγωγή Στο κεφάλαιο αυτό αναφέρουμε κάποιες εισαγωγικές έννοιες που θα μας φανούν χρήσιμες στην εργασία μας. Αρχικά κάνουμε μία πρώτη εισαγωγή στα γραφήματα και κάνουμε ένα διαχωρισμό σε κατευθυνόμενα και μη κατευθυνόμενα γραφήματα και συνεχίζοντας δίνουμε τον ορισμό της ευκλείδειας απόστασης. Ύστερα αναλύουμε τη δομή ενός δέντρου και του επικαλύπτοντος δέντρου και τέλος κάνουμε μια πρώτη εισαγωγή στα επικαλύπτοντα γραφήματα και στον παράγοντα επέκτασης. . Κεφάλαιο 2 Σε αυτό το κεφάλαιο θα παρουσιάσουμε το Θ-γράφημα, ένα γράφημα το οποίο κατασκευάζεται προσθέτοντας μια ακμή σε κάθε μία από τις κ διαφορετικές κατευθύνσεις για κάθε ένα από τα σημεία εισόδου n. Με αυτό τον τρόπο μπορούμε εύκολα να ακολουθήσουμε μια σύντομη διαδρομή από μια κορυφή σε μια άλλη για να φτάσουμε εύκολα στον προορισμό μας δηλαδή από ένα σημείο p σε ένα σημείο q. Επίσης θα δείξουμε ότι το Θ-γράφημα είναι ένα αραιό επικαλύπτον γράφημα για κάθε αυθαίρετο μικρό πραγματικό αριθμό t>1. Ξεκινώντας την ανάλυσή μας θα δώσουμε τον ορισμό του Θ-γραφήματος ύστερα τον αλγόριθμο σε μορφή ψευδοκώδικα που παράγει το Θ-περίπατο(Θ-walk), θα αναλύσουμε πως μπορούμε να χρησιμοποιήσουμε το Θ-γράφημα για να φτιάξουμε επικαλύπτοντα γραφήματα και τέλος θα δώσουμε τον τρόπο με τον οποίο κατασκευάζεται το Θ-γράφημα Κεφάλαιο 3 Σε αυτό το κεφάλαιο θα εισάγουμε την αποσύνθεση των καλώς διαχωριζόμενων ζευγών (WSPD) η οποία είναι μια δομή δεδομένων που μπορεί να χρησιμοποιηθεί για να λύσει αποτελεσματικά μια μεγάλη ποικιλία προβλημάτων απόστασης. Ύστερα θα\δώσουμε τον ορισμό της αποσύνθεσης των καλώς διαχωριζόμενων ζευγών και θα μελετήσουμε τις σχέσεις που ισχύουν αποδεικνύοντας αυτές και τέλος θα μελετήσουμε πότε μία αποσύνθεση από καλώς διαχωριζόμενα ζεύγη αποτελεί επικαλύπτον γράφημα. Κεφάλαιο 4 Σε αυτό το κεφάλαιο, θα εισαγάγουμε και να αναλύσουμε μια ιδιότητα P, τη λεγόμενη ιδιότητα του κενού (gap property). Θα ορίσουμε την απλή και την ισχυρή ιδιότητα του κενού(strong gap property) , θα αναφερθούμε στον αλγόριθμο Gap-Greedy και τέλος θα αποδείξουμε ότι ο αλγόριθμος Gap-Greedy είναι αραιό επικαλύπτον γράφημα για το S.el
dc.format.extent50 σελ.el
dc.language.isoelel
dc.publisherΠανεπιστήμιο Πελοποννήσουel
dc.rightsΑναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/gr/*
dc.subjectΘεωρία γραφημάτωνel
dc.subjectΓεωμετρία -- Πληροφορικήel
dc.titleΓεωμετρικά επικαλύπτοντα γραφήματαel
dc.typeΜεταπτυχιακή διπλωματική εργασίαel
dc.contributor.departmentΤμήμα Επιστήμης και Τεχνολογίας Υπολογιστώνel
dc.contributor.facultyΣχολή Θετικών Επιστημών και Τεχνολογίαςel
dc.contributor.masterΕπιστήμη και Τεχνολογία Υπολογιστώνel
dc.subject.keywordΕπικαλύπτοντα γραφήματαel
dc.subject.keywordΑλγόριθμοιel
dc.subject.keywordΕπικαλύπτοντα δέντραel
dc.description.abstracttranslated1 Introduction In this chapter, some introductory concepts which will be useful to the assignment are referred. At the beginning, we make a short introduction to the graphs and a separation to directed and undirected graphs and continuing we give the definition of Euclidean distance. Afterward, we analyze the structure of a tree and the spanner tree. Finally, we make a short introduction to the spanner graphs and the stretch factor. Chapter 2 In this chapter, we are going to present the Θ-graph, a graph which is created by adding an edge to each of the κ different directions for each of the n input points. In this way, we can easily follow a short path from one vertex in the graph to another in order to arrive easily at our destination, namely from one point p to a point q. Moreover we will indicate that the Θ-graph is a sparse t-spanner for any arbitrarily small given real number t > 1. Beginning our analysis, we are going to give a definition of Θ-graph, next the algorithm in pseudo code form which produces the Θ-walk. We are going to analyze how we can use the Θ-graph in order to make spanner graphs and in the end we are going to show the way in which the Θ-graph is constructed. Chapter 3 In this chapter, we are going to introduce the well-seperated pair decomposition (WSPD,, which is a data structure that can be used in order to solve effectively a great variety of proximity problems. Afterward, we are going to define the well-separated pair decomposition and we will study the relationships which are valid by proving them. In the end, we are going to study when a well- seperated pair decomposition is spanner graph. Chapter 4 In this chapter, we are going to introduce and analyze a property P, the so-called gap property. We are going to define the simple and strong gap property and we are going to refer the Gap-Greedy algorithm. Finally, we are going to prove that the Gap-Greedy algorithm is a spanner graph for S.el


Αρχεία σε αυτό το τεκμήριο

Thumbnail
Thumbnail
Thumbnail

Αυτό το τεκμήριο εμφανίζεται στις ακόλουθες συλλογές

Εμφάνιση απλής εγγραφής

Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα
Εκτός από όπου επισημαίνεται κάτι διαφορετικό, το τεκμήριο διανέμεται με την ακόλουθη άδεια:
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα