Θεωρία γραφημάτων : επίπεδα γραφήματα - ειδικές μορφές γραφημάτων - χρωματισμός γραφημάτων

Abstract

Η εργασία που ακολουθεί επιχειρεί μια εισαγωγή στη θεωρία γραφημάτων. Πρόκειται για μια ανασκόπηση στα σημαντικότερα μέρη της. Φιλοδοξία είναι να προσφέρει στον αναγνώστη τις βασικές γνώσεις και υποδομή που χρειάζεται για την περαιτέρω ενασχόλησή του με το αντικείμενο της θεωρίας γραφημάτων. Στο πρώτο κεφάλαιο δίνονται οι απαραίτητοι ορισμοί που θα διευκολύνουν τον αναγνώστη στη μελέτη της εργασίας. Στο δεύτερο κεφάλαιο παρουσιάζονται τα δέντρα και μερικές εφαρμογές τους. Στο τρίτο κεφάλαιο παρουσιάζονται τα γραφήματα των Euler και Hamilton καθώς και το πρόβλημα του Königsberg. Στο τέταρτο κεφάλαιο παρουσιάζονται ο τύπος του Euler και το θεώρημα του Kuratowski. Στο πέμπτο κεφάλαιο παρουσιάζονται μερικά ειδικά γραφήματα και οι αριθμοί Ramsey. Στο έκτο και τελευταίο κεφάλαιο παρουσιάζεται ο χρωματισμός γραφημάτων και έναν αλγόριθμοι για την επίτευξη αυτού.