Θεωρία και Αλγόριθμοι Γράφων

Στη συγκεκριμένη ενότητα πραγματοποιείται μια πρώτη γνωριμία με το μάθημα. Δίνεται το κίνητρο της ενασχόλησης με τα περιεχόμενα του μαθήματος και παρέχονται βασικές έννοιες και ορισμοί, ενώ στη συνέχεια γίνεται μια σύντομη περιγραφή των βασικών λειτουργιών που θα αναλυθούν εκτενέστερα στις επόμενες ενότητες του μαθήματος.

Λέξεις Κλειδιά: Κίνητρο, θεωρία γράφων, εισαγωγή, εφαρμογές

Στη συγκεκριμένη ενότητα πραγματοποιείται μια περιγραφή σχετικά με τη μορφή και τις ιδιότητες των γράφων. Επίσης, περιγράφονται βασικά θεωρήματα της Θεωρίας  Γράφων.

Λέξεις Κλειδιά: Γράφος, ορισμοί, θεωρήματα

Η συγκεκριμένη ενότητα παρέχει περιγραφή και παραδείγματα για τις βασικές πράξεις στους γράφους, όπως η ένωση, τομή, άθροισμα δακτυλίου, συγκερασμός, άθροισμα και άλλα. Επίσης παρουσιάζονται ειδικές περιπτώσεις γράφων, όπως ο διμερής γράφος. Ενώ στο τέλος αναλύεται ο τρόπος αναπαράστασης των γράφων και η αλγοριθμική τους απόδοση.

Λέξεις Κλειδιά: Πράξεις γράφων, διμερής γράφος,  πλήρης γράφος, αλγόριθμοι γράφων, αναπαράσταση γράφων

Σε αυτή την ενότητα παρουσιάζονται οι έννοιες του περιπάτου, ίχνους, μονοπατιού και κυκλώματος σε γράφο. Επίσης αναλύονται οι ορισμοί της εκκεντρικότητας, της απόστασης και της περιφέρειας, ενώ περιγράφονται οι γράφοι euler όπως επίσης και οι  αλγόριθμοι εύρεσης ίχνους euler,  Fleury, Hierholtzer, Tucker.

Λέξεις Κλειδιά: Περίπατος, ίχνος, μονοπάτι, κύκλωμα,  εκκεντρικότητα, απόσταση, περιφέρεια,  γράφος euler,   αλγόριθμος εύρεσης ίχνους euler,  αλγόριθμος  Fleury, αλγόριθμος  Hierholtzer, αλγόριθμος  Tucker

Στη δεύτερη ενότητα παρουσιάζεται ο κύκλος Hamilton, όπως επίσης και ο γράφος Hamilton.  Στη συνέχεια περιγράφονται βασικά Hamiltonian θεωρήματα, και αναλύεται ο αλγόριθμος εύρεσης κύκλων Hamilton. Γίνεται αναφορά στο πρόβλημα του πλησιέστερου γείτονα και οι τρόποι επίλυσης του. Τέλος παρουσιάζονται οι μαγικοί γράφοι και ο περίπατος του ιππότη/αλόγου.

Λέξεις Κλειδιά: Hamiltonian κύκλος, Hamiltonian γράφος, αλγόριθμος εύρεσης κύκλων Hamiltonian, πλησιέστερος γείτονας, μαγικοί γράφοι, περίπατος ιππότη, πείπατος αλόγου

Σε αυτή την ενότητα παρουσιάζονται τα δένδρα στους γράφους μαζί με κάποια βασικά στοιχεία, ιδιότητες και θεωρήματα. Επίσης αναλύονται το ζήτημα της απαρίθμισης των δένδρων, το Θεώρημα Πίνακα-Δένδρου Kirchoff, το θεμελιώδες κύκλωμα και η απόσταση δένδρων. Τέλος, παρουσιάζονται τα ελάχιστα ζευγνύοντα δένδρα και οι αλγόριθμοι εύρεσης τους Prim, Kruskal και Boruvka.

Λέξεις Κλειδιά: Δένδρο, απαρίθμηση δένδρων, Θεώρημα Πίνακα-Δένδρου Kirchoff , θεμελιώδες κύκλωμα, απόσταση δένδρων, ελάχιστα ζευγνύοντα δένδρα, αλγόριθμος του Prim, αλγόριθμος του Kruskal, αλγόριθμος του Boruvka

Σε αυτή την ενότητα αναλύονται εις βάθος οι αλγόριθμοι εύρεσης ελαχιστων ζευγνυόντων δένδρων Prim, Kruskal και Boruvka. Επιπλέον παρουσιάζονται οι αναλύσεις της απόδοσης του όπως επίσης και μία συγκριτική αναφορά τους.

Λέξεις Κλειδιά: Ελάχιστα ζευγνύοντα δένδρα, αλγόριθμος του Prim, αλγόριθμος του Kruskal, αλγόριθμος του Boruvka

Στη συγκεκριμένη ενότητα γίνεται μία εισαγωγή στην έννοια της συνδεσμικότητας ενός γράφου μαζί με τα θερωήματα που την αφορούν.  Στη συνέχεια αναφέρονται οι έννοιες τεμάχια γράφου, εσωτερικά ξένα μονοπάτια και τα θεωρήματα Menger και Whitney. Αναλύεται το γενικευμένο πρόβλημα συνδέσμου όπως επίσης και το πρόβλημα του ισομορφισμού. Τέλος αναλύονται οι αλγόριθμοι BFS και DFS.

Λέξεις Κλειδιά: Συνδεσμικότητα, τεμάχια γράφου, εσωτερικά ξένα μονοπάτια, θεώρημα Whitney, θεώρημα Menger, γενικευμένο πρόβλημα συνδέσμου, ισομορφισμός, αλγόριθμος BFS, αλγόριθμος DFS

Η ενότητα αυτή ασχολείται με τον επίπεδο γράφο και τον επιπεδικό γράφο, την καμπύλη Jordan. Επιπλέον εισάγεται η έννοια του εξώτερου επιπεδικού γράφου, ενώ παρουσιάζεται το θεώρημα του Euler και ο μέγιστος επίπεδος γράφος. Επιπλέον αναλύονται οι ομοιομορφικοί γράφοι, ο γεωμετρικός και ο συνδιαστικός δυαδικός.  Τέλος, αναλύεται ο αλγόριθμος επιπεδικότητας DMP.

Λέξεις Κλειδιά: Επιπεδικότητα,  επίπεδος γράφος, επιπεδικός γράφος, καμπύλη Jordan,  εξώτερος επιπεδικός γράφος, θεώρημα του Euler, μέγιστος επίπεδος γράφος, ομοιομορφικοί γράφοι,  γεωμετρικός δυαδικός, συνδιαστικός δυαδικός, αλγόριθμος επιπεδικότητας DMP

Στη συγκεκριμένη ενότητα αναλύεται εις  βάθος το θέμα του χρωματισμού ενός γράφου. Αναλύονται οι έννοιες του χρωματικού αριθμού, του μοναδικά χρωματίσιμου γράφου, του κρίσιμου γράφου, του τέλειου γράφου.  Στη συνέχεια αναλύονται ειδικές περιπτώσεις χρωματισμού γράφων και κάποια θεωρήματα, τα άνω και κάτω όρια χρωματικού αριθμού.  Περιγράφεται ο χρωματισμός επιπεδικών γράφων και ο χρωματισμός γραφών. Τέλος, γίνεται αναφορά στην εικασία των 4 χρωμάτων και παρουσιάζονται αλγόριθμοι χρωματισμού.

Λέξεις Κλειδιά: Χρωματισμός γράφου, χρωματικός αριθμός, μοναδικά χρωματίσιμος γράφος, κρίσιμος γράφος, τέλειος γράφος, ειδικές περιπτώσεις χρωματισμού γράφων,  άνω όρια χρωματικού αριθμού, κάτω όρια χρωματικού αριθμού, χρωματισμός επιπεδικών γράφων, χρωματισμός γραφών, εικασία των 4 χρωμάτων, αλγόριθμοι χρωματισμού.

Σε αυτή την ενότητα περιγράφονται οι κατευθυνόμενοι γράφοι και βασικές έννοιες γύρω από αυτούς όπως η έσω και η έξω γειτονιά, ο έσω και ο έξω βαθμός, ο γράφος τουρνουά και η συνδετότητα. Επιπλέον αναλύεται η μεταβατικότητα και οι αλγόριθμοι DFS και BFS σε κατευθυνόμενους γράφους.  Περιγράφεται ο έλεγχος ισχυρής συνεκτικότητας και η τοπολογική ταξινόμηση.

Λέξεις Κλειδιά:Κατευθυνόμενοι γράφοι, έσω γειτονιά,  έξω γειτονιά, έσω βαθμός ,  έξω βαθμός, γράφος τουρνουά, συνδετότητα, μεταβατικότητα, αλγόριθμος DFS, αλγόριθμος BFS,  έλεγχος ισχυρής συνεκτικότητας,  τοπολογική ταξινόμηση.

Αυτή η ενότητα ασχολείται με την αντιστοίχιση, το εναλλασσόμενο και αυξανόμενο μονοπάτι και τις αντιστοιχίσεις στους διγραφούς. Στη συνέχεια δίδονται περιγραφές σχετικά με τα καλύμματα και τα ανεξάρτητα σύνολα, ενώ αναλύεται ο αλγόριθμος εύρεσης μέγιστης αντιστοίχισης σε διγράφους. Τέλος, περιγράφεται αναλυτικά το πρόβλημα επιλογής προσωπικού και το πρόβλημα των σταθερών γάμων, καθώς και ο τρόπος επίλυσης τους.

Λέξεις Κλειδιά: Αντιστοίχιση,  εναλλασσόμενο μονπάτι,  αυξανόμενο μονοπάτι, καλύμματα,  αλγόριθμος εύρεσης μέγιστης αντιστοίχισης σε διγράφους, πρόβλημα επιλογής προσωπικού,  πρόβλημα των σταθερών γάμων

Στην τελευταία ενότητα του μαθήματος πραουσιάζονται τα δίκτυα με αναφορά σε πρακτικά παραδείγματα. Στη συνέχεια ορίζεται το πρόβλημα της μέγιστης ροής, καθώς και η μέθοδος  Ford Fulkerson ως μέθοδος επίλυσης της. Αναλύεται εις βάθος το θεώρημα μέγιστης ροής.

Λέξεις Κλειδιά: Δίκτυα, πρόβλημα της μέγιστης ροής, μέθοδος  Ford Fulkerson, θεώρημα μέγιστης ροής.