Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18458
Title: Αλγόριθμοι και Παίγνια Χρωματισμού Δικτύων
Authors: Φρυγανιώτης, Νικόλαος
Παπαβασιλείου Συμεών
Keywords: Χρωματισμός Γραφημάτων
Κατανεμημένοι Αλγόριθμοι
Παίγνια σε Γραφήματα
Συμμετρικές Στρατηγικές
Πιθανοτικοί Αλγόριθμοι
Issue Date: 14-Sep-2022
Abstract: Ο χρωματισμός γραφημάτων αποτελεί ένα θεμελιώδες πρόβλημα στην θεωρητική πληροφορική. Πρόκειται για ένα πρόβλημα με πολλές εφαρμογές καθώς και θεωρητικές προκλήσεις. Είναι γνωστό ότι η εύρεση ενός χρωματισμού με τον ελάχιστο δυνατό αριθμό χρωμάτων αποτελεί NP-πλήρες πρόβλημα. Μελετάται το πρόβλημα χρωματισμού ενός δικτύου. Σε αυτή την εργασία ένα δίκτυο αναπαρίσταται υπό τη μορφή ενός πεπερασμένου γραφήματος $G$, του οποίου οι κόμβοι και οι ακμές είναι οι κόμβοι του δικτύου και οι μεταξύ τους συνδέσεις, αντίστοιχα, και το οποίο θα αναφέρεται ως το υποκείμενο γράφημα του δικτύου. Έχουν προταθεί διάφοροι αλγόριθμοι εύρεσης χρωματισμού στην βιβλιογραφία, κεντρικοί και κατανεμημένοι, κάποιοι από τους οποίους αναφέρονται στην παρούσα διπλωματική. Υπάρχουν περιπτώσεις που αλγόριθμοι πετυχαίνουν έμμεσα ένα χρωματισμό. Για παράδειγμα, όταν ο χρωματισμός ενός δικτύου μοντελοποιείται ως παίγνιο, όπου οι παίκτες είναι οι κόμβοι του δικτύου. Το παίγνιο παίζεται σε γύρους, και σε κάθε γύρο οι παίκτες επιλέγουν ταυτόχρονα ένα χρώμα από ένα σύνολο διαθέσιμων χρωμάτων, ακολουθώντας μια συμμετρική στρατηγική. Όταν όλοι οι παίκτες χρωματιστούν κατάλληλα, αυτό αποτελεί μια ισορροπία Nash για το παίγνιο. Αναλύουμε ένα παίγνιο χρωματισμού δικτύου, που αρχικά προτάθηκε από τον Michael Kearns και άλλους. Για ένα γράφημα $G$, με $n$ κόμβους και μέγιστο βαθμό $\Delta$, έχει αποδειχθεί πως όταν οι παίκτες ακολουθούν μια συγκεκριμένη άπληστη πιθανοτική στρατηγική, το παίγνιο αυτό καταλήγει σε ένα κατάλληλο χρωματισμό για το γράφημα σε $O(\log n)$ γύρους, με μεγάλη πιθανότητα, δεδομένου ότι ο αριθμός των διαθέσιμων χρωμάτων σε κάθε παίκτη είναι τουλάχιστον $\Delta + 2$. Στα πλαίσια αυτής της διπλωματικής, προτείνεται μία τροποποίηση της προαναφερθείσας άπληστης στρατηγικής, και αποδεικνύεται ότι πετυχαίνει έναν κατάλληλο χρωματισμό, δεδομένου ότι ο αριθμός των διαθέσιμων χρωμάτων σε κάθε παίκτη είναι τουλάχιστον $\Delta + 1$, και έτσι προκύπτει ένας απλός πιθανοτικός κατανεμημένος αλγόριθμος για το πρόβλημα του $(\Delta + 1)$-χρωματισμού. Στη συνέχεια εξετάζουμε το πρόβλημα ανάθεσης ελαχίστων συγκρούσεων, που πρόκειται για παραλλαγή του προβλήματος χρωματισμού ενός γραφήματος. Αναλύουμε ένα παιγνιοθεωρητικό μοντέλο του παραπάνω προβλήματος, το οποίο περιγράφεται μέσω ενός παιγνίου δυναμικού. Έχει αποδειχθεί πως όταν ο αριθμός των διαθέσιμων χρωμάτων είναι μεγαλύτερος από $\Delta$, όπου $\Delta$ ο μέγιστος βαθμός του υποκείμενου γραφήματος, μια ισορροπία Nash του παίγνιου δυναμικού αποτελεί μια βέλτιστη λύση του προβλήματος ανάθεσης ελαχίστων συγκρούσεων. Εξετάζουμε έναν αλγόριθμο που συγκλίνει σε μια ισορροπία Nash αμιγούς στρατηγικής. Στα πλαίσια αυτής της εργασίας διερευνούμε επίσης την περίπτωση ενός περιορισμένου συνόλου διαθέσιμων χρωμάτων για το πρόβλημα ανάθεσης ελαχίστων συγκρούσεων, όταν δηλαδή ο αριθμός των διαθέσιμων χρωμάτων είναι λιγότερος ή ίσος με το μέγιστο βαθμό του υποκείμενου γραφήματος. Ορίζουμε ένα παίγνιο ελαττωματικού χρωματισμού, και αποδεικνύουμε ότι υπάρχει ένας πιθανοτικός κατανεμημένος αλγόριθμος που συγκλίνει σε λογαριθμικό αριθμό γύρων σε μία ανάθεση χρωμάτων, κατά την οποία κάθε κόμβος έχει το πολύ ένα δεδομένο αριθμό συγκρούσεων. Η ανάθεση αυτή αποτελεί ισορροπία Nash για το παίγνιο.
URI: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18458
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File Description SizeFormat 
Diploma_Thesis__Nikolas_Fryganiotis.pdf1.25 MBAdobe PDFView/Open


Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.