Θεωρία Γραφημάτων και Εφαρμογές

Σύντομη περιγραφή

Το μάθημα «Θεωρία Γραφημάτων και Εφαρμογές» εισάγει στις βασικές έννοιες της θεωρίας γραφημάτων με έμφαση στη μαθηματικά ακριβή διατύπωση. Συνδέει άμεσα τη θεωρία με τον σχεδιασμό αλγορίθμων σε γράφημα (π.χ. συνεκτικότητα, δέντρα, κύκλοι, ισχυρά συνεκτικές/δισυνεκτικές συνιστώσες) και με την τεκμηρίωση ορθότητας μέσω επαγωγής/αναδρομής. Ο στόχος είναι να μπορείτε να “σκέφτεστε σε γράφημα” και να αποδεικνύετε γιατί μια λύση δουλεύει.

Tip – Τι χρειάζεται προσοχή

• Ορισμοί & αποδείξεις: ακρίβεια σε έννοιες όπως συνεκτικότητα/ισχυρή συνεκτικότητα/δισυνεκτικότητα και σωστή χρήση επαγωγής–αναδρομής.
• Αλγοριθμική σκέψη σε γράφημα: σωστή μοντελοποίηση, επιλογή κατάλληλης διάτρεξης/δομής (π.χ. δέντρο επικάλυψης) και έλεγχος ορθότητας βήμα-βήμα.

Τι κερδίζεις από αυτό το μάθημα

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