Γενικά
Θεωρία Γραφημάτων
Διδάσκων : Χ. Παπαδόπουλος
Περιγραφή:
Bασικές έννοιες γραφημάτων. Δένδρα. Διαδρομές και αποστάσεις. Συνδεσιμότητα. Διαμερίσεις. Αναπαράσταση γραφημάτων. Σκελετικά δένδρα, απαρίθμηση, καταμέτρηση και παραγοντοποίηση. Μονοπάτια και κύκλοι Euler και Hamilton. Αριθμοί ελαχίστης κάλυψης, κυριαρχίας, ανεξαρτησίας. Eπίπεδα γραφήματα. Θεώρημα Kuratowski (χωρίς απόδειξη). Χρωματισμοί κορυφών, πρόβλημα των τεσσάρων και πέντε χρωμάτων. Δυϊκά γραφήματα. Δίκτυα ροής. Δυσεπίλυτα προβλήματα γραφημάτων. Υλοποίηση και μελέτη αλγορίθμων στο εργαστήριο. Αλγόριθμοι: Dijkstra, Prim, συνεκτικότητας, δένδρου, επιπεδότητας, μεγίστης σύζευξης, κινέζου ταχυδρόμου, χρωματικών πολυωνύμων, ροής.
Μαθησιακοί Στόχοι Μαθήματος:
Τα γραφήματα αποτελούν ένα διαδεδομένο τύπο δεδομένων στην επιστήμη των υπολογιστών και οι αλγόριθμοι για τον χειρισμό τους είναι θεμελιώδους σημασίας για τους κλάδους της πληροφορικής και των μαθηματικών.
Ο στόχος του μαθήματος είναι
- η εισαγωγή στην θεωρία γραφημάτων
- η κατανόηση αλγοριθμικών τεχνικών για προβλήματα που σχετίζονται με γραφήματα.
Λέξεις κλειδιά: Γραφήματα, Συνεκτικότητα, Σκελετικά Δέντρα, Eulerian & Hamiltonian γραφήματα, Χρωματικός αριθμός, Κλίκα, Ανεξάρτητα σύνολα, Κάλυμμα κορυφών, Επίπεδα γραφήματα