Παρουσίαση/Προβολή
Αλγοριθμικη Θεωρία Γραφημάτων (ΠΜΣ Πληροφορική) και Θεωρία Γραφημάτων (ΔΠΜΣ ΑΛΜΑ)
(Μ101) - Αρχοντία Γιαννοπούλου
Περιγραφή Μαθήματος
Επισκόπηση βασικών εννοιών της Θεωρίας Γραφημάτων.
Συνεκτικότητα, δισυνεκτικά γραφήματα, το Θεώρημα του Menger, Το Θεώρημα του Tutte για την 3-συνεκτικότητα.
Χρωματισμός ακμών και κορυφών.
Καλύμματα και ταιριάσματα σε γραφήματα και πίνακες.
Επίπεδα γραφήματα, τοπολογικός ισομορφισμός, δυικά γραφήματα, πυκνότητα και επιπεδότητα, Το θεώρημα του Kuratowski.
Ειδικές κλάσεις γραφημάτων: δομικές ιδιότητες και έλεγχος του ανήκειν.
Δενδροπλάτος: διαχωριστές και δυναμικός προγραμματισμός.
Θεωρία Ελασσόνων Γραφημάτων.
Ώρες διδασκαλίας:
Τετάρτη 13:00 – 15:00 στην Αίθουσα Ζ
Παρασκευή 12:00 - 14:00 στην Αίθουσα Ε
Ημερομηνία δημιουργίας
Τρίτη 12 Φεβρουαρίου 2019
-
Προαπαιτούμενα
Είναι επιθυμητό οι φοιτητές να έχουν βασικές γνώσεις Θεωρίας Γραφημάτων. Επιπλέον, καλό θα ήταν να έχουν στοιχειώδεις γνώσεις από τα Διακριτά Μαθηματικά, τη Λογική, και τη Θεωρία Συνόλων. Τέλος, είναι καλό οι φοιτητές να έχουν αποκτήσει εξοικείωση με την έννοια του αλγορίθμου και την ανάλυση της πολυπλοκότητάς του και γνώσεις ισοδύναμες με ένα προπτυχιακό μάθημα Αλγορίθμων και Πολυπλοκότητας.
Βιβλιογραφία
- Reinhard Diestel. Graph Theory
-
J. A. Bondy and U. S. R. Murty. Graph Theory with Applications
- Marek Cygan et al. Parameterized Algorithms
- Laszlo Lovasz and Michael D. Plummer. Matching Theory
- Jon Kleinberg and Éva Tardos. Σχεδιασμός Αλγορίθμων
- Douglas B. West. Combinatorial Mathematics
- Δημήτριος Θηλυκός. Σημειώσεις στη Θεωρία Γραφημάτων (μπορείτε να το βρείτε σε pdf στην η-τάξη)
Ώρες διδασκαλίας
Ώρες διδασκαλίας:
Τετάρτη 13:00 – 15:00 στην Αίθουσα Ζ
Παρασκευή 12:00 - 14:00 στην Αίθουσα Ε