Θεωρία Γραφημάτων (7ΕΠ02)
Διδάσκων : Ευριπίδης Μάρκου
ΕίδοςΕπιλογής (υποχρεωτικό)
Εξάμηνο7
ΠερίοδοςΧΕ
ECTS5
Ώρες Θεωρίας3
Ώρες Εργαστηρίου
Περιγραφή
Βασικοί παράμετροι γραφημάτων. Μοντελοποίηση προβλημάτων με τη βοήθεια γράφων. Προσανατολισμένοι γράφοι, πλήρεις, διμερείς, επίπεδοι, υπογράφοι, ισομορφισμός γράφων. Συνεκτικές συνιστώσες, κύκλοι Euler, κύκλοι Hamilton: Εφαρμογές στα δίκτυα τηλεπικοινωνιών. Κωδικοποίηση γράφων. Δένδρα επικάλυψης (minimum spanning tree). Αλγόριθμοι διάσχισης. Βέλτιστα μονοπάτια. Ροές σε δίκτυα, μέγιστη ροή, θεώρημα max flow-min cut, δίκτυα με άνω και κάτω φράγματα χωρητικότητας. Πρόβλημα ταιριάσματος. Προβλήματα NP - πλήρη. Κομβική επικάλυψη. Προβλήματα χρωματισμού. Προβλήματα μέγιστης κλίκας και πυκνότερου υπογράφου.
Μαθησιακοί Στόχοι
  • Μοντελοποίηση προβλημάτων με τη βοήθεια γράφων
  • Ανάλυση και απόδειξη ιδιοτήτων των γραφημάτων
  • Αλγόριθμοι σε γραφήματα
Συγγράμματα/Βιβλιογραφία
  • Θεωρία και Αλγόριθμοι Γράφων, Ιωάννης Μανωλόπουλος, Απόστολος Παπαδόπουλος, Κωνσταντίνος Τσίχλας, ΕΚΔΟΣΕΙΣ ΝΕΩΝ ΤΕΧΝΟΛΟΓΙΩΝ ΜΟΝ. ΕΠΕ, 1η/2013, ΑΘΗΝΑ, 33134148
  • Εισαγωγή στους Γράφους, Κυρούσης Λευτέρης Μ., Μπούρας Χρήστος Ι., Σπυράκης Παύλος Γ., Σταματίου Γ, Γ. ΔΑΡΔΑΝΟΣ - Κ. ΔΑΡΔΑΝΟΣ Ο.Ε., 1η έκδ./1999, ΑΘΗΝΑ, 31356
Τρόπος Εξέτασης
Μία σειρά ασκήσεων κάθε 3 εβδομάδες, ενδιάμεση γραπτή εξέταση (πρόοδος), τελικές γραπτές εξετάσεις.
Υλικό
Σημειώσεις