Θεωρία Γραφημάτων (ΤΒ1)

Το μάθημα αποτελεί εισαγωγή σε ένα θεμελιώδη κλάδο των μαθηματικών, τη θεωρία γραφημάτων. Αποσκοπεί στην παροχή βασικών γνώσεων γραφημάτων για την απρόσκοπτη χρήση των αντίστοιχων θεωρητικών εννοιών και μεθοδολογιών σε πρακτικά προβλήματα και εφαρμογές της επιστήμης υπολογιστών, πληροφοριακών συστημάτων και ανθρωπο-κεντρικών εφαρμογών.

Η ύλη στοχεύει στην εισαγωγή των σπουδαστών στις βασικές έννοιες και σε χρήσιμα αποτελέσματα της θεωρίας γραφημάτων και την εξοικείωσή τους με πληθώρα σχετικών εννοιών μέσω καθημερινών παραδειγμάτων. Παράλληλα μέσω ασκήσεων και πρακτικών εργασιών θα τους βοηθήσει να ανακαλύψουν βασικά εργαλεία ανάλυσης γραφημάτων τα οποία είναι διαθέσιμα στο Διαδίκτυο.

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

Συνοπτικά το περιεχόμενο του μαθήματος καλύπτει τις βασικές έννοιες και τους βασικούς ορισμούς που άπτονται των γραφημάτων ως μαθηματικές έννοιες. Καλύπτει πληθώρα θεματικών περιοχών όπως η συνεκτικότητα, οι κύκλοι & και τα μονοπάτια, οι τομές, η επιπεδότητα, ο χρωματισμός γράφων, οι τυχαίοι περίπατοι και η ομαδοποίηση κόμβων (clustering). Σε κάθε επιμέρους περιοχή, παρουσιάζονται οι βασικοί ορισμοί των μεγεθών ενδιαφέροντος, ορίζεται τυπικά το κάθε πρόβλημα, π.χ. τι σημαίνει χρωματισμός γράφου, εύρεση κύκλου Euler, κλπ., και παρουσιάζονται σημαντικά και χρήσιμα αποτελέσματα (θεωρήματα) και αλγόριθμοι (μεθοδολογίες) που μπορούν να χρησιμεύσουν στους φοιτητές και τις φοιτήτριες σε επόμενα μαθήματα στο Τμήμα Πληροφορικής.

Σε επίπεδο εβδομαδιαίας διδασκαλίας, το περιεχόμενο οργανώνεται ως εξής:

1η εβδομάδα:

Βασικοί ορισμοί: Γραφήματα, υπογράφοι, κλπ.

2η εβδομάδα:

Βασικοί ορισμοί: Μονοπάτια & κύκλοι

3η εβδομάδα: Δένδρα

Συνεκτικότητα γράφων (διάσχιση γράφων, ροές και τομές)

4η εβδομάδα:

Αποστάσεις και διαδρομές σε γράφους

5η εβδομάδα:

Γραφήματα Euler και Hamilton

6η εβδομάδα:

Επίπεδα γραφήματα

7η εβδομάδα:

Καλύψεις γράφων

8η εβδομάδα:

Αλγεβρική θεωρία γραφημάτων. Πίνακας γειτονίας, Λαπλασιανός πίνακας, ιδιοτιμές και ιδιοδιανύσματα πίνακα γειτονίας.

9η εβδομάδα:

Χρωματισμός γράφων

10η εβδομάδα:

Τέλεια ταιριάσματα σε γραφήματα

11η εβδομάδα:

Τυχαίοι περίπατοι σε γραφήματα

12η εβδομάδα:

Ομαδοποίηση (clustering) σε γράφους.

13η εβδομάδα:

Επανάληψη και επίλυση ενδεικτικών ασκήσεων

1. Θεωρία και Αλγόριθμοι Γράφων, Ιωάννης Μανωλόπουλος, Απόστολος Παπαδόπουλος, Κωνσταντίνος Τσίχλας.
2. ΑΛΓΟΡΙΘΜΙΚΗ ΘΕΩΡΙΑ ΓΡΑΦΗΜΑΤΩΝ, ΣΤΑΥΡΟΣ ΝΙΚΟΛΟΠΟΥΛΟΣ, ΓΕΩΡΓΙΑΔΗΣ ΛΟΥΚΑΣ, ΠΑΛΗΟΣ ΛΕΩΝΙΔΑΣ
3. Graph Theory [electronic resource], Reinhard Diestel

Διαλέξεις δια ζώσης + ατομικές σειρές ασκήσεων

• Χρήση ηλεκτρονικών σημειώσεων
• Υποστήριξη διδασκαλίας μέσω της ηλεκτρονικής πλατφόρμας e-class

Γραπτή εξέταση + σειρές ασκήσεων