| Γνωστική Περιοχή: | Υπολογιστικών και Εφαρμοσμένων Μαθηματικών | ||
| Εξάμηνο: | 5ο | ||
| Κωδικός: | 52403 | ||
| Τύπος Μαθήματος: | Επιλογής | ||
| Ώρες Διδασκαλίας: | Θεωρία: 4 | Άσκηση: 0 | Εργαστήριο: 0 |
| ECTS : | 5 | ||
| Ιστοσελίδα Eclass: | |||
| Διδάσκοντες Μαθήματος: | |||
| Περίγραμμα μαθήματος: | Για να δείτε ή να αποθηκεύσετε το αρχείο πατήστε εδώ. | ||
Περιεχόμενο
Βασικοί παράμετροι γραφημάτων. Μοντελοποίηση προβλημάτων με τη βοήθεια γραφημάτων. Προσανατολισμένα γραφήματα, πλήρη, διμερή, επίπεδα γραφήματα, υπογραφήματα, ισομορφισμός γραφημάτων. Συνεκτικές συνιστώσες, κύκλοι Euler, κύκλοι Hamilton: Εφαρμογές στα δίκτυα τηλεπικοινωνιών. Κωδικοποίηση γραφημάτων. Δένδρα επικάλυψης (minimum spanning tree). Αλγόριθμοι διάσχισης. Βέλτιστα μονοπάτια. Ροές σε δίκτυα, μέγιστη ροή, θεώρημα max flow-min cut, δίκτυα με άνω και κάτω φράγματα χωρητικότητας. Πρόβλημα ταιριάσματος. Προβλήματα NP – πλήρη. Κομβική επικάλυψη. Προβλήματα χρωματισμού. Προβλήματα μέγιστης κλίκας και πυκνότερου υπογραφήματος.
Βιβλιογραφία
- Μανωλόπουλος Ι., Παπαδόπουλος Α., Τσίχλας Κ., Θεωρία και Αλγόριθμοι Γράφων. Κωδικός βιβλίου στον Εύδοξο: 33134148
- Κυρούσης Λ. Μ., Μπούρας Χ. Ι., Σπυράκης Π. Γ., Σταματίου Γ., Εισαγωγή στους γράφους. Κωδικός βιβλίου στον Εύδοξο: 31356
