Σχεδιασμός και ανάλυση αλγορίθμων για συνδυαστικά προβλήματα σε τυχαία γραφήματα τομής ετικετών
Loading...
Files
Date
Authors
Χριστοδούλου, Φίλιππος
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Στην παρούσα διπλωματική εργασία ορίζουμε τα τυχαία γραφήματα τομής ετικετών και εξετάζονται ως προς ορισμένες σημαντικές γραφοθεωρητικές ιδιότητές τους. Ένα τυχαίο γράφημα τομής ετικετών παράγεται αντιστοιχώντας σε κάθε κορυφή ένα τυχαίο υποσύνολο ενός πεπερασμένου σύμπαντος Μ από m στοιχεία, τα οποία ονομάζουμε ετικέτες, βάζοντας μία ακμή μεταξύ δύο κορυφών αν και μόνο αν τα αντίστοιχα σύνολά τους έχουν μη κενή τομή. Συγκεκριμενοποιώντας την κατανομή που ακολουθεί το τυχαίο υποσύνολο ετικετών που αντιστοιχείται σε κάθε κορυφή παίρνουμε τελικά διαφορετικά στιγμιότυπα τυχαίων γραφημάτων τομής ετικετών. Στο μοντέλο τυχαίων γραφημάτων τομής, κάθε στοιχείο i του M επιλέγεται ανεξάρτητα από κάθε κορυφή με πιθανότητα p.
Όπως θα δούμε για ορισμένες τιμές των παραμέτρων m και p, το μοντέλο Gn,m,p είναι ισοδύναμο με το μοντέλο Gn,p, δηλαδή με το μοντέλο τυχαίων γραφημάτων στο οποίο κάθε ακμή του εμφανίζεται στοχαστικά ανεξάρτητα με πιθανότητα p, γνωστό στη βιβλιογραφία και ως Erdős–Rényi μοντέλο. Ακόμη, στο μοντέλο τυχαίων γραφημάτων τομής ετικετών το υποσύνολο του M που αντιστοιχείται σε κάθε κορυφή έχει σταθερό αριθμό στοιχείων. Τα γραφήματα αυτά θεωρούνται αρκετά ρεαλιστικά μοντέλα, σε σύγκριση με τα κλασσικά τυχαία γραφήματα και χρησιμοποιούνται σε πολλές πρακτικές εφαρμογές, ιδιαίτερα σε αλγοριθμικά θέματα δικτύων. Το γεγονός αυτό οφείλεται στη στοχαστική εξάρτηση που υπονοείται για την ύπαρξη των ακμών του γραφήματος. Στην εργασία αυτή, αρχικά παρουσιάζουμε μερικά χαρακτηριστικά αποτελέσματα από τη σχετική βιβλιογραφία για τα μοντέλα αυτά. Ακολούθως, μελετάμε το μέγεθος της μέγιστης κλίκας στο μοντέλο Gn,m,p όπως επίσης και υπάρχοντες αλγορίθμους που εξετάζονται πειραματικά για την περιοχή τιμών 0 < α <= 1. Τέλος, προτείνουμε και αναλύουμε δύο καινούριους αλγορίθμους που έχουν ως στόχο την εύρεση της μέγιστης κλίκας με αρκετά μεγάλη πιθανότητα στο μοντέλο Gn,m,p.
Description
Keywords
Tυχαίο γράφημα τομής, Μέγιστη κλίκα, Πιθανοτικός αλγόριθμος