Η παρούσα διπλωματική εργασία διερευνά τους αλγόριθμους και τις μεθόδους χρωματισμού γραφημάτων. Αρχικά γίνεται παρουσίαση των βασικών εννοιών της Θεωρίας Γράφων και παρουσιάζονται ιστορικά στοιχεία έτσι ώστε να γίνει πιο κατανοητό και σαφές το θέμα που πραγματεύεται η εργασία. Όπου αναφέρεται ο όρος «γράφος» εννοείται ότι είναι απλός, πεπερασμένος και μη κατευθυνόμενος. Στη συνέχεια γίνεται αναφορά στον χρωματισμό γράφων, τους τομείς στους οποίους απαντάται, η σημασία του και κάποιες εφαρμογές του. Επίσης παρουσιάζεται το θεώρημα των τεσσάρων χρωμάτων και η σημασία του στην εξέλιξη της θεωρίας γράφων. Ακόμα, παρουσιάζονται 6 ευριστικοί αλγόριθμοι χρωματισμού γράφων με έμφαση στα χαρακτηριστικά τους και στη σειρά επιλογής των κορυφών. Τέλος γίνεται εφαρμογή του αλγόριθμου DSatur στον γράφο που αναπαριστά τον χάρτη των Ηνωμένων πολιτειών της Αμερικής. Η έξοδός του αφορά στον χρωματισμό του συγκεκριμένου γράφου με τον ελάχιστο δυνατό αριθμό χρωμάτων. Συνολικά χρησιμοποίησε για τον χρωματισμό του γράφου άρα και του αντίστοιχου χάρτη των Η.Π.Α. 4 χρώματα, για τις 48 κορυφές που διαθέτει. Στον συγκεκριμένο αλγόριθμο δεν υπήρχε η δυνατότητα να αλλάξουμε τη σειρά επιλογής των κορυφών. Τέλος, παρουσιάζονται τα αποτελέσματα και τα συμπεράσματα τις εργασίας.
This thesis explores graph coloring algorithms and methods. First, the basic concepts of Graph Theory are introduced and historical background is presented in order to make the topic addressed in the thesis more understandable and clear. Wherever the term "graph" is mentioned it is understood to be simple, finite and undirected. Then reference is made to graph coloring, the areas in which it is found, its importance and some of its applications. The four-color theorem and its importance in the development of graph theory is also presented. Furthermore, 6 heuristic graph coloring algorithms are presented with emphasis on their characteristics and the order of vertex selection. Finally, the DSatur algorithm is applied to the graph representing the map of the United States of America. Its output concerns the coloring of the given graph with the minimum possible number of colors. In total he used for coloring the graph and therefore the corresponding map of the United States of America 4 colors, for the 48 vertices available. In this algorithm there was no possibility to change the order of selection of the vertices. Finally, the results and conclusions of the paper are presented.
Democritus University of Thrace
