Γεωμετρικά επικαλύπτοντα γραφήματα

Abstract

1 Εισαγωγή Στο κεφάλαιο αυτό αναφέρουμε κάποιες εισαγωγικές έννοιες που θα μας φανούν χρήσιμες στην εργασία μας. Αρχικά κάνουμε μία πρώτη εισαγωγή στα γραφήματα και κάνουμε ένα διαχωρισμό σε κατευθυνόμενα και μη κατευθυνόμενα γραφήματα και συνεχίζοντας δίνουμε τον ορισμό της ευκλείδειας απόστασης. Ύστερα αναλύουμε τη δομή ενός δέντρου και του επικαλύπτοντος δέντρου και τέλος κάνουμε μια πρώτη εισαγωγή στα επικαλύπτοντα γραφήματα και στον παράγοντα επέκτασης. . Κεφάλαιο 2 Σε αυτό το κεφάλαιο θα παρουσιάσουμε το Θ-γράφημα, ένα γράφημα το οποίο κατασκευάζεται προσθέτοντας μια ακμή σε κάθε μία από τις κ διαφορετικές κατευθύνσεις για κάθε ένα από τα σημεία εισόδου n. Με αυτό τον τρόπο μπορούμε εύκολα να ακολουθήσουμε μια σύντομη διαδρομή από μια κορυφή σε μια άλλη για να φτάσουμε εύκολα στον προορισμό μας δηλαδή από ένα σημείο p σε ένα σημείο q. Επίσης θα δείξουμε ότι το Θ-γράφημα είναι ένα αραιό επικαλύπτον γράφημα για κάθε αυθαίρετο μικρό πραγματικό αριθμό t>1. Ξεκινώντας την ανάλυσή μας θα δώσουμε τον ορισμό του Θ-γραφήματος ύστερα τον αλγόριθμο σε μορφή ψευδοκώδικα που παράγει το Θ-περίπατο(Θ-walk), θα αναλύσουμε πως μπορούμε να χρησιμοποιήσουμε το Θ-γράφημα για να φτιάξουμε επικαλύπτοντα γραφήματα και τέλος θα δώσουμε τον τρόπο με τον οποίο κατασκευάζεται το Θ-γράφημα Κεφάλαιο 3 Σε αυτό το κεφάλαιο θα εισάγουμε την αποσύνθεση των καλώς διαχωριζόμενων ζευγών (WSPD) η οποία είναι μια δομή δεδομένων που μπορεί να χρησιμοποιηθεί για να λύσει αποτελεσματικά μια μεγάλη ποικιλία προβλημάτων απόστασης. Ύστερα θα\δώσουμε τον ορισμό της αποσύνθεσης των καλώς διαχωριζόμενων ζευγών και θα μελετήσουμε τις σχέσεις που ισχύουν αποδεικνύοντας αυτές και τέλος θα μελετήσουμε πότε μία αποσύνθεση από καλώς διαχωριζόμενα ζεύγη αποτελεί επικαλύπτον γράφημα. Κεφάλαιο 4 Σε αυτό το κεφάλαιο, θα εισαγάγουμε και να αναλύσουμε μια ιδιότητα P, τη λεγόμενη ιδιότητα του κενού (gap property). Θα ορίσουμε την απλή και την ισχυρή ιδιότητα του κενού(strong gap property) , θα αναφερθούμε στον αλγόριθμο Gap-Greedy και τέλος θα αποδείξουμε ότι ο αλγόριθμος Gap-Greedy είναι αραιό επικαλύπτον γράφημα για το S.