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

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

Στόχοι Μαθήματος

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

Προαπαιτούμενες Γνώσεις

Βασικές γνώσεις αλγορίθμων

Περιεχόμενα

Εισαγωγικά Στοιχεία Μονοπάτια και κύκλοι Δένδρα Συνδεσμικότητα Επιπεδικότητα Χρωματισμός Κατευθυνόμενοι Γράφοι Αντιστοιχίσεις και καλύμματα Δίκτυα και ροές