Θεωρία Γραφημάτων

Βασικές παράμετροι γράφων, μοντελοποίηση προβλημάτων με τη βοήθεια γράφων. Ειδικές κατηγορίες γράφων: πλήρεις, διμερείς, επίπεδοι γράφοι, γράφοι διαστημάτων, χορδικοί γράφοι. Ισομορφισμός γράφων. Συνεκτικές συνιστώσες, κύκλοι Euler, κύκλοι Hamilton: εφαρμογές στα δίκτυα τηλεπικοινωνιών. Προβλήματα χρονοπρογραμματισμού, critical paths. Ροές σε δίκτυα, μέγιστη ροή, θεώρημα max flow - min cut, δίκτυα με άνω και κάτω φράγματα χωρητικότητας. Μέγιστη ροή ελάχιστου κόστους - εφαρμογές στη σχεδίαση δικτύων. Διασχίσεις Euler, συνθήκες ύπαρξης, κατευθυνόμενη και μη κατευθυνόμενη περίπτωση. Το πρόβλημα του κινέζου ταχυδρόμου. Πρoβλήματα matching και δίκτυα μεταφοράς. Το πρόβλημα του μεγίστου ανεξαρτήτου συνόλου (stability γράφου) - εφαρμογές: ικανοποίηση αιτήσεων στα δίκτυα. Προβλήματα χρωματισμού (chromatic number, chromatic index) - εφαρμογές: παράλληλα και κατανεμημένα συστήματα. Προβλήματα μέγιστης κλίκας και πυκνότερου υπογράφου. Πολυωνυμικές περιπτώσεις σε ειδικές τοπολογίες γράφων  (Chordal, interval, perfect γράφοι).