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

Κωδικός
7ΕΠ02
Επίπεδο
Προπτυχιακό
Είδος
Επιλογής (υποχρεωτικό)
Εξάμηνο
7
Περίοδος
ΧΕ
ECTS
5
Ώρες Θεωρίας
3
Ώρες Εργαστηρίου
-

Περιγραφή

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

Μαθησιακοί Στόχοι

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

Συγγράμματα - Βιβλιογραφία

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

Τρόπος Εξέτασης

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

Υλικό

Σημειώσεις