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