Τμήμα : Γενικό
Τομέας : Μαθηματικών
Κωδικός : Νέο
Εξάμηνο : 6ο
Ροή : Μ : Μαθηματικά
Κατ' επιλογήν υποχρεωτικό.
Ώρες Θεωρίας : 3
Ώρες Εργαστηρίου : 0
ΔΕΠ :
Α. Παπαϊωάννου, Επίκουρος Καθηγητής.
Περιεχόμενο του μαθήματος :
Εισαγωγή. Ορισμοί - Υπογραφήματα - Συνεκτικά γραφήματα δέντρα - Δίκτυα - οικονομικότερο παράγων δέντρο (The connector problem). Γραφήματα Euler και Hamilton ικανή και αναγκαία συνθήκη για γράφημα Euler αλγόριθμος Fleury. Γραφήματα Hamilton: ικανές συνθήκες - Αναγκαίες συνθήκες Αλγόριθμος Kaufmann. Δυνάμεις γραφημάτων - Γραφημάτων - Γραφήματα Hamilton και συνεκτικότητα. Επίπεδα γραφήματα - χρωματισμοί τύπος Euler-Θεώρημα Kuratowski Δυικά γραφήματα-γραφήματα welch-Powell θεώρημα 5 και 4 χρωμάτων θεώρημα brooks. Χρωματισμοί πλευρών: Θεώρημα Vizing. Συνεκτικότητα - ταιριάσματα. Συνεκτικότητα. Θεώρημα menger (για κορυφές, για πλευρές). Max-flow, min cut. ταιριάσματα: θεώρημα Hall (ή του γάμου) ταιριάσματα σε διμερή γραφήματα Personnel assignement problem - Σταθεροί γάμοι. Πίνακες - Δέντρα. Πίνακας γειτνίασης και πρόσπτωσης Matrix-tree theorem. Απαρίθμιση δέντρων με ονομασία. Τύπος Cayler - κώδικας Prufer.