Βασικοί παράμετροι γραφημάτων. Μοντελοποίηση προβλημάτων με τη βοήθεια γράφων. Προσανατολισμένοι γράφοι, πλήρεις, διμερείς, επίπεδοι, υπογράφοι, ισομορφισμός γράφων. Συνεκτικές συνιστώσες, κύκλοι Euler, κύκλοι Hamilton: Εφαρμογές στα δίκτυα τηλεπικοινωνιών. Κωδικοποίηση γράφων. Δένδρα επικάλυψης (minimum spanning tree). Αλγόριθμοι διάσχισης. Βέλτιστα μονοπάτια. Ροές σε δίκτυα, μέγιστη ροή, θεώρημα max flow-min cut, δίκτυα με άνω και κάτω φράγματα χωρητικότητας. Πρόβλημα ταιριάσματος. Προβλήματα NP - πλήρη. Κομβική επικάλυψη. Προβλήματα χρωματισμού. Προβλήματα μέγιστης κλίκας και πυκνότερου υπογράφου.
Χειμ. Εξάμηνο 2015 - 2016. Μάθημα επιλογής 4ου έτους.
Πρόγραμμα: Τετάρτη 16.00-18.00, Αίθ. 4
Παρασκευή 10.00-12.00, Αίθ. 4
Προαπαιτούμενες γνώσεις ή/και σχετικά μαθήματα:
Διακριτά Μαθηματικά, Δομές Δεδομένων, Αλγόριθμοι και Πολυπλοκότητα
Μαθησιακοί Στόχοι:
- Μοντελοποίηση προβλημάτων με τη βοήθεια γράφων
- Ανάλυση και απόδειξη ιδιοτήτων των γραφημάτων
- Αλγόριθμοι σε γραφήματα
Μέθοδοι Διδασκαλίας:
Διαλέξεις θεωρίας (4 ώρες/εβδομάδα) και επιπλέον φροντιστηριακά μαθήματα με επίλυση ασκήσεων (2 ώρες/ 3 εβδομάδες).
Τρόπος Εξέτασης:
Μία σειρά ασκήσεων κάθε 3 εβδομάδες, ενδιάμεση γραπτή εξέταση (πρόοδος), τελικές γραπτές εξετάσεις.
Υλικό: Σημειώσεις
Δείτε εδώ την περιγραφή των θεμάτων που έχουμε συζητήσει.