Θεωρία Γραφημάτων
Κωνσταντίνος Κόκκινος
Επίκ. Καθηγητής
Μαθησιακά Αποτελέσματα
Με την επιτυχή ολοκλήρωση του μαθήματος ο/η φοιτητής/τρια θα είναι σε θέση να:
- ορίζει και να περιγράφει έννοιες, ιδιότητες και χαρακτηριστικά των γράφων,
- διακρίνει μεταξύ διαφόρων τύπων γράφων και να επιλέγει τον κατάλληλο τύπο για διάφορες εφαρμογές,
- επεκτείνει την αλγοριθμική του σκέψη σε προβλήματα σχετικά με τη θεωρία γραφημάτων,
- αναγνωρίζει το ρόλο των γραφημάτων ως μοντέλο για μια μεγάλη ποικιλία προβλημάτων εξόρυξη γνώσης από δεδομένα χρήσης,
- μοντελοποιεί και εφαρμόζει της παραπάνω έννοιες σε πραγματικά προβλήματα που άπτονται εφαρμογών δικτύων,
- μελετά και αναλύει δεδομένα για την εξόρυξη γνώσης με χρήση εργαλείων και λογισμικών οπτικοποίησης γραφημάτων,
- κατανοεί και εφαρμόζει μετρικές κεντρικότητας και άλλες μετρικές δικτύων,
- αξιολογεί, εξηγεί και παρουσιάζει τα αποτελέσματα που προκύπτουν από την ανάλυση δικτύου που εφαρμόζει για την εξαγωγή συμπερασμάτων.
Ενδεικτικό Περιεχόμενο Μαθήματος
Ο κύριος σκοπός του μαθήματος είναι η κατανόηση της θεωρίας γραφημάτων και των εφαρμογών της στη μοντελοποίηση και αλγοριθμική επίλυση πρακτικών προβλημάτων σχετικών με τα δίκτυα δεδομένων. Στο μάθημα περιλαμβάνονται ατομικές ασκήσεις, περιληπτική συγγραφή και παρουσίαση σχετικών ερευνητικών εργασιών και εφαρμογών με χρήση εργαλείων ανάλυσης δικτύων όπως Python (NetworkX), R (tidyverse), Javascript (cytoscape js, sigma) και λογισμικών οπτικοποίησης δικτύων/γραφημάτων όπως Gephi, Neo4j, Cytoscape, Pajek, NodeXL κ.α.
- Ορισμοί και είδη γραφημάτων, Ισομορφισμός Γραφημάτων
- Αναπαράσταση Γραφημάτων
- Πράξεις Γραφημάτων
- Δένδρα, Δένδρα Επικάλυψης, Ελάχιστα Δένδρα Επικάλυψης, Αλγόριθμος Prim και Kruskal, διάσχιση δένδρων
- Συνεκτικές συνιστώσες, διαδρομές Euler και Hamilton
- Αλγόριθμοι Ελάχιστων Μονοπατιών
- Εφαρμογές Θεωρίας Γράφων σε Κοινωνικά Δίκτυα
- Εφαρμογές Θεωρίας Γράφων σε Βιολογικά Δίκτυα
- Εκκεντρικότητα και άλλες μετρικές δικτύων
- Εφαρμογές ανάλυσης δικτύων και εξόρυξη γνώσης από δεδομένα χρήσης στην μουσική, στις βιβλιογραφικές αναφορές, τα κρυπτονομίσματα κ.α.