Αντικείμενο:

• Ορισμοί δικτύων,γραφημάτων,δρόμων συνεκτικότητας, τοπολογικής διάταξης, αποθήκευση δικτύων.
   

Περιεχόμενo:

• Μαθηματική μορφή προβλημάτων δικτύων: πρόβλημα ροής ελαχίστου κόστους(ΠΡΕΚ), ειδικές περιπτώσεις του ΠΡΕΚ(πρόβλημα μεταφοράς, πρόβλημα ανάθεσης, πρόβλημα ελαχίστων δρόμων, πρόβλημα μεγίστης ροής, προβλήματα δέντρων).Γενικεύσεις του ΠΡΕΚ(γενικευμένο πρόβλημα πλανόδιων, ΠΡΕΚ, ΠΡΕΚ πολλών προϊόντων, κυρτό κόστος), μετασχηματισμοί προβλημάτων δικτύων, συνθήκες βελτιστότητας λύσεων του ΠΡΕΚ.Το πρόβλημα ροής ελαχίστου κόστους: εφαρμογές, αλγόριθμος πρωτεύον simplex(περιγραφή, επίλυση γενικών ΠΡΕΚ, κανόνες αντικύκλωσης, προγραμματισμός).Αλγόριθμος ελαχίστου μέσου κυκλώματος, εξειδίκευση του αλγόριθμου simplex.Πρόβλημα μεταφοράς: εφαρμογές, εξειδίκευση αλγόριθμου πρωτεύοντος simplex(Barr Glover και Klingman),Ουγγρικός αλγόριθμος, αλγόριθμος δέντρων Παπαρρίζου, αλγόριθμος δασών των Achatz, Kleinschmindt and Paparrizos, αλγόριθμος πλειστηριασμού του Μπερτσέκα.Πρόβλημα μεγίστης ροής: εφαρμογές, ελάχιστες τομές, αλγόριθμος αυξανόντων δρόμων, αλγόριθμος ελαχίστων αυξανόντων δρόμων.