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