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

Εισαγωγή: Ορισμοί, Υπογραφήματα, Συνεκτικά γραφήματα δέντρα, Δίκτυα, οικονομικότερο παράγων δέντρο (The connector problem). Γραφήματα Euler και Hamilton, ικανή και αναγκαία συνθήκη για γράφημα Euler, αλγόριθμος Fleury. Γραφήματα Hamilton: ικα- νές συνθήκες, αναγκαίες συνθήκες, αλγόριθμος Kaufmann. Γραφήματα Hamilton και συνεκτικότητα. Επίπεδα γραφήματα, χρωματισμοί τύπος Euler, Θεώρημα Kuratowski Δυϊκά γραφήματα, Χρωματισμοί κορυφών αλγόριθμος Welsh-Powell. θεώρημα 5 και 4 χρωμάτων θεώρημα Brooks. Χρωματισμοί πλευρών: Θεώρημα Vizing. Συνεκτικότητα-ταιριάσματα. Συνεκτικότητα. Θεώρημα Menger (για κορυφές, για πλευρές). Max-flow, min cut. Ταιριάσματα: θεώρημα Hall (ή του γάμου) ταιριάσματα σε διμερή γραφήματα Personnel assignement problem, σταθεροί γάμοι. Πίνακες: Πίνακας γειτνίασης και πρόσπτωσης Matrix-tree theorem. Απαρίθμηση δέντρων με ονομασία. Τύπος Cayley-κώδικας Pruter