Θεωρία Γράφων (7ΕΠ02)

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