Απεικόνιση Γραφημάτων Με Έμφαση Στις Ιδιότητες Μονοπατιών

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 φορές η ευκλείδεια απόσταση μεταξύ των ακραίων σημείων. Στο τέλος, συγκεντρωνόμαστε στην μέση ανάλυση των ιδιοτήτων του συνδετικού δικτύου.