Μάθημα : Θεωρία Γραφημάτων (ΠΜΣ Μαθηματικών) Αλγοριθμικη Θεωρία Γραφημάτων (ΠΜΣ Πληροφορική) και Θεωρία Γραφημάτων (ΔΠΜΣ ΑΛΜΑ)
MATH909 - Αρχοντία Γιαννοπούλου, Δημήτριος Θηλυκός
Περιγραφή Μαθήματος
Το πρώτο μάθημα θα γίνει την Τετάρτη 07 Οκτωβρίου 11-13 στην Αίθουσα Α21 του Τμήματος Μαθηματικών.
Το μάθημα θα καλύψει τις εξής ενότητες
Επισκόπηση βασικών εννοιών της Θεωρίας Γραφημάτων.
Συνεκτικότητα, δισυνεκτικά γραφήματα, το Θεώρημα του Menger, Το Θεώρημα του Tutte για την 3-συνεκτικότητα.
Χρωματισμός ακμών και κορυφών.
Καλύμματα και ταιριάσματα σε γραφήματα και πίνακες.
Επίπεδα γραφήματα, τοπολογικός ισομορφισμός, δυικά γραφήματα, πυκνότητα και επιπεδότητα, Το θεώρημα του Kuratowski.
Ειδικές κλάσεις γραφημάτων: δομικές ιδιότητες και έλεγχος του ανήκειν.
Δενδροπλάτος: διαχωριστές και δυναμικός προγραμματισμός.
Θεωρία Ελασσόνων Γραφημάτων.
Ώρες διδασκαλίας:
Στο Τμήμα Μαθηματικών:
Τετάρτη 11:00 – 13:00 στην Αίθουσα Α21
Πέμπτη 11:00 - 13:00 στην Αίθουσα Α21
Στο Τμήμα Πληροφορικής και Τηλεπικοινωνιών
Τετάρτη 11:00 - 13:00 στην Αίθουσα Z
Πέμπτη 11:00 - 13:00 στην Αίθουσα B
Ο χώρος διεξαγωγής κάθε διάλεξης θα ανακοινώνεται έγκαιρα στην eclass.
Το πρώτο μάθημα θα γίνει στο Τμήμα Μαθηματικών την Τετάρτη 7 Οκτωβρίου 2026.
Προαπαιτούμενα
Είναι επιθυμητό, αλλά όχι απαραίτητο, οι φοιτητές να έχουν στοιχειώδεις γνώσεις Θεωρίας Γραφημάτων. Επιπλέον, καλό θα ήταν να έχουν στοιχειώδεις γνώσεις από τα Διακριτά Μαθηματικά, τη Λογική, και τη Θεωρία Συνόλων. Βασικό προαπαιτούμενο του μαθήματος είναι η μαθηματική ωριμότητα.
Βιβλιογραφία
- Reinhard Diestel. Graph Theory
-
J. A. Bondy and U. S. R. Murty. Graph Theory with Applications
- Laszlo Lovasz and Michael D. Plummer. Matching Theory
- Jon Kleinberg and Éva Tardos. Σχεδιασμός Αλγορίθμων
- Douglas B. West. Combinatorial Mathematics
- Δημήτρης Ζώρος - Δημήτριος Θηλυκός. Σημειώσεις μαθήματος Θεωρίας Γραφημάτων (από συνεχή αναθεώρηση) (μπορείτε να το βρείτε σε pdf στην η-τάξη)