Please use this identifier to cite or link to this item:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/13682
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ανάργυρος Μ. Οικονόμου | |
dc.date.accessioned | 2018-07-23T09:26:20Z | - |
dc.date.available | 2018-07-23T09:26:20Z | - |
dc.date.issued | 2018-1-15 | |
dc.date.submitted | 2018-1-15 | |
dc.identifier.uri | http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/13682 | - |
dc.description.abstract | Η μονότονη απεικόνιση ενός γραφήματος G, είναι μια ευθύγραμμη απεικόνιση του G έτσι ώστε κάθε ζευγάρι κορυφών να συνδέεται, μέσω ενός μονοπατιού που είναι μονότονο ως προς κάποια κατεύθυνση. Μια ευθύγραμμη απεικόνιση Γ ενός δένδρου T είναι κυρτή, αν αντικαταστήσουμε κάθε φύλλο με μια ημιευθεία, το επίπεδο διαμερίζεται σε μη-φραγμένα κυρτά πολύγωνα.Τα δένδρα, σαν μια ειδική κατηγορία γραφημάτων, έχουν υπάρξει το επίκεντρο αρκετών άρθρων και πρόσφατα οι He και He περιέγραψαν πώς να παράγουμε μια μονότονη απεικόνιση ενός δένδρου με n κόμβους σε ένα πλέγμα μεγέθους 12n x 12n.Στην παρούσα διπλωματική εργασία, παρουσιάζουμε έναν απλό αλγόριθμο ο οποίος κατασκευάζει για κάθε ριζωμένο δένδρο μια μονότονη απεικόνιση σε πλέγμα μεγέθους το πολύ 3/4*(n+1) x 3/4*(n+1). Επιπλέον, περιγράφουμε πως να κατασκευάσουμε μια κυρτή απεικόνιση ενός δένδρου σε πλέγμα με μέγεθος το πολύ n x n.Δεν κάνουμε χρήση κάποιας τεχνικής βασισμένης στη θεωρία αριθμών, το οποίο αποτελεί ένα κοινό χαρακτηριστικό όλων των προηγούμενων προσεγγίσεων, αλλά κάνουμε χρήση μερικών απλών γεγονότων από τη γεωμετρία, τα οποία μπορούν να εκφραστούν πιο αναλυτικά.Στο τελευταίο κεφάλαιο, εξετάζουμε ένα διαφορετικό θέμα. Αρχικά, αποδεικνύουμε ένα φράγμα συγκέντρωσης για τον αριθμό των σημείων που κυριαρχούν απευθείας την αρχή των αξόνων στον d-διάστατο χώρο κάτω από μερικές συνθήκες ''ανεξαρτησίας''. Έπειτα συνεχίζουμε περιγράφοντας πως να κατασκευάσουμε ένα συνεκτικό γράφημα δεδομένου ενός συνόλου σημείων στον d-διάστατο χώρο. Μετά, παρουσιάζουμε έναν απλό αλγόριθμο τοπικής δρομολόγησης, όπου η απόσταση που διανύεται είναι το πολύ ρίζα d φορές η ευκλείδεια απόσταση μεταξύ των ακραίων σημείων. Στο τέλος, συγκεντρωνόμαστε στην μέση ανάλυση των ιδιοτήτων του συνδετικού δικτύου. | |
dc.language | Greek | |
dc.subject | απεικόνιση γραφημάτων | |
dc.subject | υπολογιστική γεωμετρία | |
dc.subject | μονότονη απεικόνιση | |
dc.subject | κυρτή απεικόνιση | |
dc.subject | συνδετικό δίκτυο | |
dc.subject | τοπική δρομολόγηση | |
dc.title | Απεικόνιση Γραφημάτων Με Έμφαση Στις Ιδιότητες Μονοπατιών | |
dc.type | Diploma Thesis | |
dc.description.pages | 73 | |
dc.department | Τομέας Μαθηματικών ΣΕΜΦΕ | |
dc.organization | ΕΜΠ, Τμήμα Ηλεκτρολόγων Μηχανικών & Μηχανικών Υπολογιστών | |
Appears in Collections: | Διπλωματικές Εργασίες - Theses |
Files in This Item:
File | Size | Format | |
---|---|---|---|
DT2018-0010.pdf | 806.07 kB | Adobe PDF | View/Open |
Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.