Θεωρία Γραφημάτων

Βασικοί παράμετροι γραφημάτων. Μοντελοποίηση προβλημάτων με τη βοήθεια γράφων. Προσανατολισμένοι γράφοι, πλήρεις, διμερείς, επίπεδοι, υπογράφοι, ισομορφισμός γράφων. Συνεκτικές συνιστώσες, κύκλοι Euler, κύκλοι Hamilton: Εφαρμογές στα δίκτυα τηλεπικοινωνιών. Κωδικοποίηση γράφων. Δένδρα επικάλυψης (minimum spanning tree). Αλγόριθμοι διάσχισης. Βέλτιστα μονοπάτια. Ροές σε δίκτυα, μέγιστη ροή, θεώρημα max flow-min cut, δίκτυα με άνω και κάτω φράγματα χωρητικότητας. Πρόβλημα ταιριάσματος. Προβλήματα NP – πλήρη. Κομβική επικάλυψη. Προβλήματα χρωματισμού. Προβλήματα μέγιστης κλίκας και πυκνότερου υπογράφου.

• Μοντελοποίηση προβλημάτων με τη βοήθεια γράφων
• Ανάλυση και απόδειξη ιδιοτήτων των γραφημάτων
• Αλγόριθμοι σε γραφήματα

• Θεωρία και Αλγόριθμοι Γράφων, Ιωάννης Μανωλόπουλος, Απόστολος Παπαδόπουλος, Κωνσταντίνος Τσίχλας, ΕΚΔΟΣΕΙΣ ΝΕΩΝ ΤΕΧΝΟΛΟΓΙΩΝ ΜΟΝ. ΕΠΕ, 1η/2013, ΑΘΗΝΑ, 33134148
• Εισαγωγή στους Γράφους, Κυρούσης Λευτέρης Μ., Μπούρας Χρήστος Ι., Σπυράκης Παύλος Γ., Σταματίου Γ, Γ. ΔΑΡΔΑΝΟΣ – Κ. ΔΑΡΔΑΝΟΣ Ο.Ε., 1η έκδ./1999, ΑΘΗΝΑ, 31356

Μία σειρά ασκήσεων κάθε 3 εβδομάδες, ενδιάμεση γραπτή εξέταση (πρόοδος), τελικές γραπτές εξετάσεις.

Σημειώσεις