ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ - ΕΡΓΑΣΙΑ ΕΞΑΜΗΝΟΥ
Θέμα Εργασίας: Αλγόριθμοι χρωματισμού γράφων
Περίληψη εργασίας
Το πρόβλημα του χρωματισμού γραφήματος είναι ένα NP‐hard πρόβλημα συνδυαστικής βελτιστοποίησης, με πρακτικές εφαρμογές σε διάφορους κλάδους επιχειρησιακής έρευνας. Αφορά την ανάθεση ενός χρώματος σε κάθε κορυφή ενός γραφήματος έτσι ώστε γειτονικές κορυφές να χρωματίζονται με διαφορετικό χρώμα όπως φαίνεται στο παρακάτω σχήμα, ενώ παράλληλα χρησιμοποιείται ο ελάχιστος αριθμός διαφορετικών χρωμάτων. Στην παρούσα εργασία ζητείται η υλοποίηση τεσσάρων αλγορίθμων χρωματισμού γραφημάτων και η εφαρμογή τους σε γνωστά προβλήματα από τη βιβλιογραφία.
Αποσπάσματα κώδικα
- read_data.cpp: ανάγνωση δεδομένων car-s-92.stu, καταγραφή φοιτητών ανά εξέταση.
- set_ops.cpp: εύρεση τομής ενός std::set
με ένα άλλο std::set . - random_numbers.cpp, random_numbers2.cpp: παραγωγή ψεύδο-τυχαίων ακέραιων τιμών στο διάστημα [1,V].
- greedy_coloring.cpp: απεικόνιση γράφου ως λίστα γειτνίασης και greedy χρωματισμός του γράφου.
- count_common_elements.cpp εύρεση πλήθους κοινών στοιχείων ανάμεσα σε 2 vectors.
- 2d_array.cpp δυναμικός δισδιάστατος πίνακας στη C++ (και στη C).
- graph_example.cpp μια υλοποίηση της κλάσης graph για το πρόβλημα και μια υλοποίηση της συνάρτησης ελέγχου έγκυρου χρωματισμού του γραφήματος
- Stepik - Data structures - LEXICON
- pdf αναφοράς