Θεωρία Γραφημάτων και Εφαρμογές

Επίσημο περίγραμμα μαθήματος του ΤΜΗΥΠ (Πανεπιστήμιο Πατρών), όπως δημοσιεύεται στη σελίδα του μαθήματος και στο συνημμένο αρχείο «Περίγραμμα Μαθήματος». Το κείμενο παρατίθεται αυτούσιο, χωρίς τα πρότυπα οδηγιών του εντύπου.

Στόχοι

• Γνώση των κύριων κατηγοριών γραφημάτων, των θεμελιωδών σχέσεων που χαρακτηρίζουν ένα γράφημα, και των χαρακτηριστικών εφαρμογών τους. Κατανόηση βασικών ερωτημάτων και προβλημάτων, σχετικά με τα γραφήματα. Γνώση τεχνικών ανάλυσης ενός γραφήματος. Γνώση υπολογιστικών μεθόδων για γραφήματα. Δεξιότητα στην απάντηση θεωρητικών ερωτημάτων σχετικά με τα γραφήματα, καθώς και στην επίλυση υπολογιστικών προβλημάτων.

Περιεχόμενο (ύλη)

Εισαγωγή στις βασικές έννοιες και τεχνικές της θεωρίας των γραφημάτων, με έμφαση στην μαθηματικά ακριβή περιγραφή των εννοιών. Χρήση της θεωρίας στον σχεδιασμό αλγορίθμων για προβλήματα γραφημάτων, και στην επαλήθευση της ορθότητάς τους. Καλύπτονται: Μονοπάτια , κύκλοι, ίχνη Euler. Έννοιες συνεκτικότητας και δισυνεκτικότητας, αντίστοιχες έννοιες συνεκτικών και δισυνεκτικών συνιστωσών. Βασική θεωρία δέντρων. Δέντρα επικάλυψης και ιδιότητές τους, στοιχειώδεις κύκλοι σαν βάση του γραμμικού χώρου των κύκλων. H μαθηματική επαγωγή στα γραφήματα. Εφαρμογή της μαθηματικής επαγωγής σε ενδεικτικά προβλήματα ( χρωματισμός, μέγιστα μονοπάτια, επιπεδότητα). Σχεδιασμός αναδρομικών αλγορίθμων για γραφήματα, χρησιμοποιώντας ανάλυση σε (δι)συνεκτικές συνιστώσες. Εφαρμογή στα παραπάνω ενδεικτικά προβλήματα. Αναδρομικοί αλγόριθμοι για δέντρα και δυναμικός προγραμματισμός. Επαναληπτικοί αλγόριθμοι για δέντρα, υπολογισμός κέντρων δέντρου.

Αξιολόγηση

Γραπτή εξέταση (Ελληνική γλώσσα). Περιλαμβάνει Ερωτήσεις Σύντομης Απάντησης και Επίλυση Προβλημάτων. Αξιολογούνται: η πληρότητα της γνώσης της θεωρίας, η ακρίβεια και ορθότητα των λύσεων. Οι απαντήσεις των θεμάτων των εξετάσεων δημοσιεύονται στην ιστοσελίδα του μαθήματος.

Βιβλιογραφία

Σ. Κοσμαδάκης, “Εισαγωγή στα Γραφήματα, Θεωρία – Ασκήσεις”. Kenneth H. Rosen “Διακριτά μαθηματικά και εφαρμογές τους, 7η Έκδοση”.

-Συναφή επιστημονικά περιοδικά: