ΘΠ10 Θεωρία Γράφων

• Κ17 - Αλγόριθμοι και Πολυπλοκότητα

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