Θεωρία Γραφημάτων και Εφαρμογές
Σταύρος Κοσμαδάκης
ΣΗΜΑΝΤΙΚΗ ΑΝΑΚΟΙΝΩΣΗ Το μάθημα θα εξεταστεί, το 2023 - 24, με ανοιχτά βιβλία και σημειώσεις. Οι φοιτητές θα μπορούν να έχουν μαζύ τους ΜΟΝΟ τα βιβλία και τις σημειώσεις του μαθήματος, και δικές τους χειρόγραφες σημειώσεις.
Το μάθημα αποτελεί εισαγωγή στις βασικές έννοιες και τεχνικές της θεωρίας των γραφημάτων. Δίνεται έμφαση στην περιγραφή και χρήση των εννοιών με μαθηματικά ακριβή τρόπο. Εξετάζεται η εφαρμογή της θεωρίας (i) στον σχεδιασμό αλγορίθμων για προβλήματα γραφημάτων, και (ii) στην επαλήθευση της ορθότητας αυτών των αλγορίθμων. Καλύπτονται: Συνεκτικότητα, ισχυρή συνεκτικότητα, δισυνεκτικότητα, επαγωγή και αναδρομή για γραφήματα, βασική θεωρία δέντρων, στοιχειώδεις κύκλοι.
Το κύριο σύγγραμμα του μαθήματος είναι οι διδακτικές σημειώσεις: Εισαγωγή στα Γραφήματα, Θεωρία - Ασκήσεις, του Σ. Κοσμαδάκη. Όλη η απαιτούμενη ύλη, καθώς και η ορολογία που χρησιμοποιείται στις παραδόσεις, καλύπτεται στις διδακτικές σημειώσεις.
Το δεύτερο σύγγραμμα είναι το βιβλίο: Διακριτά μαθηματικά και εφαρμογές τους, 8η Έκδοση, του Kenneth H. Rosen. Υπάρχει στον Εύδοξο. Περιέχει επιπρόσθετα παραδείγματα και ασκήσεις, αλλά μόνο για ένα μέρος της απαιτούμενης ύλης. Μπορεί να χρησιμοποιηθεί για εμπέδωση των μαθηματικών δεξιοτήτων που χρειάζονται στο μάθημα.
ΛιγότεραΣΗΜΑΝΤΙΚΗ ΑΝΑΚΟΙΝΩΣΗ Το μάθημα θα εξεταστεί, το 2023 - 24, με ανοιχτά βιβλία και σημειώσεις. Οι φοιτητές θα μπορούν να έχουν μαζύ τους ΜΟΝΟ τα βιβλία και τις σημειώσεις του μαθήματος, και δικές τους χειρόγραφες σημειώσεις.
Το μάθημα αποτελεί εισαγωγή στις βασικές έννοιες και τεχνικές της θεωρίας των γραφημάτων. Δίνεται έμφαση στην περιγραφή και χρήση των εννοιών με μαθηματικά ακριβή τρόπο. Εξετάζεται η εφαρμογή της θεωρίας (i) στον σχεδιασμό αλγορίθμων για προβλήματα γραφημάτων, και (ii) στην επαλήθευση της ορθότητας αυτών των αλγορίθμων. Καλύπτονται: Συνεκτικότητα, ισχυρή συνεκτικότητα, δισυνεκτικότητα, επαγωγή και αναδρομή για γραφήματα, βασική θεωρία δέντρων, στοιχειώδεις κύκλοι.
Το κύριο σύγγραμμα του μαθήματος είναι οι διδακτικές σημειώσεις: Εισαγωγή στα Γραφήματα, Θεωρία - Ασκήσεις, του Σ. Κοσμαδάκη. Όλη η απαιτούμενη ύλη, καθώς και η ορολογία που χρησιμοποιείται στις παραδόσεις, καλύπτεται στις διδακτικές σημειώσεις.
Το δεύτερο σύγγραμμα είναι το βιβλίο: Διακριτά μαθηματικά κα
ΣΗΜΑΝΤΙΚΗ ΑΝΑΚΟΙΝΩΣΗ Το μάθημα θα εξεταστεί, το 2023 - 24, με ανοιχτά βιβλία και σημειώσεις. Οι φοιτητές θα μπορούν να έχουν μαζύ τους ΜΟΝΟ τα βιβλία και τις σημειώσεις του μαθήματος, και δικές τους χειρόγραφες σημειώσεις.
Το μάθημα αποτελεί εισαγωγή στις βασικές έννοιες και τεχνικές της θεωρίας των γραφημάτων. Δίνεται έμφαση στην περιγραφή και χρήση των εννοιών με μαθηματικά ακριβή τρόπο. Εξετάζεται η εφαρμογή της θεωρίας (i) στον σχεδιασμό αλγορίθμων για προβλήματα γραφημάτων, και (ii) στην επαλήθευση της ορθότητας αυτών των αλγορίθμων. Καλύπτονται: Συνεκτικότητα, ισχυρή συνεκτικότητα, δισυνεκτικότητα, επαγωγή και αναδρομή για γραφήματα, βασική θεωρία δέντρων, στοιχειώδεις κύκλοι.
Το κύριο σύγγραμμα του μαθήματος είναι οι διδακτικές σημειώσεις: Εισαγωγή στα Γραφήματα, Θεωρία - Ασκήσεις, του Σ. Κοσμαδάκη. Όλη η απαιτούμενη ύλη, καθώς και η ορολογία που χρησιμοποιείται στις παραδόσεις, καλύπτεται στις διδακτικές σημειώσεις.
Το δεύτερο σύγγραμμα είναι το βιβλίο: Διακριτά μαθηματικά κα
Περίγραμμα
Διδακτικό Υλικό
Στο πεδίο "Έγγραφα" καταχωρούνται:
(i) Τα συγγράμματα του μαθήματος.
(ii) Συμπληρωματικό υλικό (άλλα βιβλία, σημειώσεις κοκ), που μπορεί να χρησιμοποιηθεί ως επιπλέον βοήθημα - για ορισμένα από τα θέματα που καλύπτει το μάθημα.
(iii) Μια σειρά από "Συνοπτικά Μαθήματα" και "Προτεινόμενες Ασκήσεις".
Τα "Συνοπτικά Μαθήματα" είναι καταγραφές παραδόσεων του μαθήματος - η σειρά τους δεν είναι χρονολογική. Περιέχουν αναλυτικές λεπτομέρειες της ύλης που έχει παρουσιαστεί στις παραδόσεις, μαζύ με επιπλέον παραδείγματα, παρατηρήσεις κλπ. Δίνονται παραπομπές σε σχετικά μέρη του άλλου διδακτικό υλικού, για επιπλέον μελέτη.
Οι "Προτεινόμενες Ασκήσεις" είναι ενδεικτικές του αναμενόμενου επιπέδου κατανόησης, της σχετικής ύλης.
Στο πεδίο "Έγγραφα" καταχωρούνται:
(i) Τα συγγράμματα του μαθήματος.
(ii) Συμπληρωματικό υλικό (άλλα βιβλία, σημειώσεις κοκ), που μπορεί να χρησιμοποιηθεί ως επιπλέον βοήθημα - για ορισμένα από τα θέματα που καλύπτει το μάθημα.
(iii) Μια σειρά από "Συνοπτικά Μαθήματα" και "Προτεινόμενες Ασκήσεις".
Τα "Συνοπτικά Μαθήματα" είναι καταγραφές παραδόσεων του μαθήματος - η σειρά τους δεν είναι χρονολογική. Περιέχουν αναλυτικές λεπτομέρειες της ύλης που έχει παρουσιαστεί στις παραδόσεις, μαζύ με επιπλέον παραδείγματα, παρατηρήσεις κλπ. Δίνονται παραπομπές σε σχετικά μέρη του άλλου διδακτικό υλικού, για επιπλέον μελέτη.
Οι "Προτεινόμενες Ασκήσεις" είναι ενδεικτικές του αναμενόμενου επιπέδου κατανόησης, της σχετικής ύλης.
Στοιχεία προτασιακής λογικής. Σύνολα, σχέσεις, ιδιότητες σχέσεων. Σχέσεις ισοδυναμίας. Μαθηματική επαγωγή.
Κατευθυνόμενα και μη-κατευθυνόμενα γραφήματα. Διαδρομές, μονοπάτια, ίχνη, κύκλοι. Προσβασιμότητα και συναφείς σχέσεις.
Συνεκτικά γραφήματα. Συνεκτικές συνιστώσες μη-κατευθυνόμενου γραφήματος. Κομβικά σημεία, γέφυρες.
Mη-επεκτάσιμα μονοπάτια. Αναδρομή και επαγωγή για συνεκτικά γραφήματα. Αναδρομή και επαγωγή για άκυκλα συνεκτικά γραφήματα.
Μοναδικότητα μονοπατιών, ιδιότητα Helly. Δυναμικός προγραμματισμός για δέντρα. Επαναληπτική διάτρεξη δέντρου. Επαγωγή για δέντρα: κέντρα δέντρου, εύρεση μέγιστου μονοπατιού.
Άθροισμα κύκλων. Ο γραμμικός χώρος των κύκλων ενός γραφήματος, ενώσεις κύκλων χωρίς κοινές ακμές.
Στοιχειώδεις κύκλοι ως προς δεδομένο δέντρο επικάλυψης. Βάσεις του γραμμικού χώρου των κύκλων.
Ισχυρά συνεκτικά κατευθυνόμενα γραφήματα. Ισχυρά συνεκτικές συνιστώσες, ιδιότητές τους. Γράφημα των ισχυρά συνεκτικών συνιστωσών.
Δισυνεκτικά γραφήματα, ως προς ακμές, και ιδιότητές τους. Δισυνεκτικές συνιστώσες ως προς ακμές, και ιδιότητές τους. Γράφημα των δισυνεκτικών συνιστωσών ως προς ακμές.
Δισυνεκτικά γραφήματα ως προς κορυφές, δισυνεκτικές συνιστώσες ως προς κορυφές, γράφημα των δισυνεκτικών συνιστωσών ως προς κορυφές.
