Περίληψη : | Τα περιεχόμενα αυτής της εργασίας αναπτύσσονται ως εξής. Στο Κεφάλαιο 1 εισάγουμε ορισμένες βασικές έννοιες της θεωρίας Γράφων και δίνουμε τους αυστηρούς ορισμούς των κλάσεων γράφων που θα χρησιμοποιήσουμε. Στο Κεφάλαιο 2 αρχικά ορίζουμε και αποδεικνύουμε βασικές ιδιότητες των γράφων διαστημάτων και των συγγενών τους, καθώς και το πώς συνδέονται αυτές οι κλάσεις γράφων μεταξύ τους. Στη συνέχεια παρουσιάζουμε αλγόριθμους για την επίλυση κλασικών προβλημάτων (μέγιστη κλίκα, χρωματισμός κορυφών, ανεξάρτητο σύνολο, κάλυψη από κλίκες) σε χορδικούς γράφους. Στο Κεφάλαιο 3 εξετάζουμε το πρόβλημα του χρωματισμού ακμών ενός γράφου διαστημάτων, δηλαδή την ανάθεση χρωμάτων στις ακμές του, ούτως ώστε οι γειτονικές ακμές να λαμβάνουν διαφορετικά χρώματα. Στο Κεφάλαιο 4 εξετάζουμε το πρόβλημα του χρωματισμού κορυφών με περιορισμούς πληθυκότητας σε γράφους διαστημάτων, δηλαδή την ανάθεση χρωμάτων στις κορυφές του γράφου, έτσι ώστε οι κορυφές που γειτνιάζουν να έχουν διαφορετικό χρώμα και κάθε χρώμα να χρωματίζει έως ένα συγκεκριμένο αριθμό κορυφών. Στο Κεφάλαιο 5 μελετάμε το χρωματισμό κορυφών σε γράφους κυκλικών τόξων και στο Κεφάλαιο 6 μελετάμε τον άμεσο χρωματισμό κορυφών σε γράφους διαστημάτων και κυκλικών τόξων. 0 άμεσος χρωματισμός κορυφών διαφοροποιείται από τον απλό χρωματισμό κορυφών στο ότι δε γνωρίζει εκ των προτέρων την τοπολογία του γράφου. Στο Κεφάλαιο 7 παρουσιάζουμε το πρόβλημα του μέγιστου χρωματισμού κορυφών σε γράφους διαστημάτων. Σε κάθε κορυφή του γράφου αποδίδουμε κάποιο βάρος και αναζητάμε ένα χρωματισμό έτσι ώστε το άθροισμα των μέγιστων βαρών των κορυφών του κάθε χρώματος να είναι ελάχιστο. Τέλος, στο Κεφάλαιο 8 εξετάζουμε το πρόβλημα του χρονοπρογραμματισμού ενός συνόλου εργασιών με διάταξη διαστημάτων και στόχο την ελαχιστοποίηση του χρόνου ολοκλήρωσης των εργασιών σε ένα σύνολο ισοδύναμων μεταξύ τους επεξεργαστών.
|
---|