ΤΜΗΜΑ ΜΑΘΗΜΑΤΙΚΩΝ ΚΑΙ ΕΦΑΡΜΟΣΜΕΝΩΝ ΜΑΘΗΜΑΤΙΚΩΝ - ΠΑΝΕΠΙΣΤΗΜΙΟ ΚΡΗΤΗΣ
Σημαντικό:Κάντε εγγραφή στο μάθημα, ώστε να λαμβάνετε άμεσα όλες τις ανακοινώσεις και να μπορείτε να συμμετέχετε στις συζητήσεις για το μάθημα και σε όποια άλλη δραστηριότητα προκύψει.
Είδαμε παραδείγματα ενίσχυσης πρότασης και το Θεώρημα του Γάμου. Έγινε εισαγωγή στην Συνδυαστική: αρχή του πολλαπλασιασμού, πλήθος συναρτήσεων από ένα σύνολο \(A\) σε ένα σύνολο \(B\), ημιανεξαρτησία, πλήθος διατεταγμένων επιλογών, μεταθέσεις συνόλου.
Είδαμε τους συνδυασμούς \(n\) ανά \(k\) και σχετικά παραδείγματα. Επίσης, είδαμε τις διαμερίσεις και τους συνδυασμούς με επανάθεση, μαζί με μια πληθώρα από σχετικά παραδείγματα.
Υπάρχει ένα σημαντικό λάθος στο πρώτο ερώτημα του παραδείγματος στις διαφάνειες 9-11. Δείτε το αρχείο με τις διαφάνειες για να δείτε την σωστή απάντηση.
Υπάρχει ένα λάθος απροσεξίας στην 15η διαφάνεια (έχουμε 5 γυναίκες και 3 άνδρες και όχι αντίστροφα όπως φαίνεται στην αρχη). Επίσης, στην 10η διαφάνεια η απάντηση είναι \(\binom{2n}{n}\). Δείτε τις διορθωμένες διαφάνειες.
Είδαμε τους πολυωνυμικούς συντελεστές, το πολυωνυμικό θεώρημα (multinomial theorem) και μερικά παραδείγματα συνδυαστικών αποδείξεων ταυτοτήτων. Είδαμε την αρχή του εγκλεισμού-αποκλεισμού και το πλήθος των επί συναρτήσεων \([m] \to [n]\).
(Παράγραφοι 4.2, 4.3 και 4.4 του [1] και παράγραφοι 8.5 και 8.6 του [3] - Η απόδειξη του πολυωνυμικού θεωρήματος δεν εντοπίζεται στην προτεινόμενη βιβλιογραφία)
Στην διάλεξη αυτή λύνουμε όλες τις ασκήσεις. Επειδή το βίντεο είναι πολύ μεγάλο, μπορείτε να δείτε πρώτα τις λύσεις από το φυλλάδιο των λύσεων και να ανατρέχετε στο αντίστοιχο τμήμα του βίντεο αν χρειάζεστε επιπλέον επεξηγήσεις για κάποια άσκηση.
Παρατήρηση: Όπως πολύ σωστά επισημάθηκε στο forum, υπάρχει ένα ζήτημα με την Άσκηση 9. Επειδή είναι παρόμοια με άσκηση που έχει λυθεί σε προηγούμενη διάλεξη, η λύση της δεν δόθηκε στην διάλεξη και η αρχική λύση στο φυλλάδιο των λύσεων ήταν ελλιπής. Δείτε τις λύσεις στο φυλλάδιο των λύσεων για την πλήρη απάντηση.
Έγινε μια εισαγωγή στην Θεωρία Γραφημάτων: είδαμε τον ορισμό του απλού γραφήματος, των γειτονικών ακμών/κορυφών, της γειτονιάς, του βαθμού ακμών/κορυφών και του \(r\)-κανονικού γραφήματος και το Θεώρημα των Χειραψιών με μερικές εφαρμογές του. Ακόμα είδαμε παραδείγματα ειδικών γραφημάτων, την έννοια του υπογραφήματος και του επαγόμενου υπογραφήματος και ορίσαμε την ισομορφία γραφημάτων, ενώ είδαμε μερικές ιδιότητες που μοιράζονται ισόμορφα γραφήματα. Κλείσαμε με παραδείγματα μοντελοποίησης απλών προβλημάτων με την βοήθεια γραφημάτων.
Υπάρχει μια παράλειψη στα σημεία 34:30-34:50, καθώς από την κορυφή (ΚΧΒ/ΚΧ), έχουμε ακμή προς την κορυφή (/ΚΚΧΧΒ), οπότε θα έχουμε τελικά επιπλέον δύο μονοπάτια που λύνουν το πρόβλημα.
Συνεχίσαμε με την ισομορφία γραφημάτων και ορίσαμε το μονοπάτι. Είδαμε ότι ένας ισομορφισμός γραφημάτων αντιστοιχεί μονοπάτια μήκους \(n\) σε μονοπάτια μήκους \(n\). Είδαμε πληθώρα παραδειγμάτων. Κυκλώματα, κύκλοι, προσιτότητα, η προσιτότητα ως σχέση ισοδυναμίας, συνεκτικότητα, συνεκτικές συνιστώσες, απόσταση κορυφών, η απόσταση ως μετρική, διάμετρος απλού γραφήματος.
Στο βίντεο, στις χρονικές στιγμές 00:45-01:20 αντί των \(E\cap E=\emptyset\) και \(E\cup E = \ldots\) θα έπρεπε να αναφέρεται \(E\cap E^C=\emptyset\) και \(E\cup E^C = \ldots\) αντίστοιχα.
Είδαμε τις λύσεις του 2ου φυλλαδίου. Ακόμα είδαμε μερικές προτάσεις σχετικές με την διάμετρο ενός απλού συνεκτικού γραφήματος και αρκετά παραδείγματα σχετικά με την διάμετρο και την ισομορφία γραφημάτων.
Είδαμε τις έννοιες της άρθρωσης και της γέφυρας, καθώς και εκείνες του δέντρου και του δάσους. Είδαμε ότι κάθε συνεκτικό γράφημα περιέχει ένα παράγων δέντρο και κάθε γράφημα έχει κάποιο παράγων δάσος. Αφού ορίσαμε τα φύλλα, είδαμε ότι ένα δέντρο \(n\geq 2\) κορυφών έχει τουλάχιστον δύο φύλλα. Χαρακτηρίσαμε πλήρως ένα δέντρο. Στη συνέχεια είδαμε διάφορες γενικεύσεις του απλού γραφήματος (κατευθυνόμενα γραφήματα, βρόγχους, πολλαπλές ακμές, βάρη). Αναφερθήκαμε στο πρόβλημα του περιπλανώμενου πωλητή, ορίσαμε το ελάχιστο παράγων δέντρο και είδαμε τον αλγόριθμο του Kruskal.
(Παράγραφοι 5.5, 5.6 και 5.7 του [1] και παράγραφος 10.4 του [3])
Είδαμε τους αλγόριθμους Floyd-Warshall και Dijkstra. Είδαμε και χαρακτηρίσαμε τα διμερή γραφήματα. Ορίσαμε τον χρωματικό αριθμό \(\chi(G)\) του γραφήματος \(G\), είδαμε κάποια άμεσα άνω και κάτω φράγματά του και είδαμε ότι το \(G\) είναι διμερές αν και μόνο αν \(\chi(G)\leq 2\).
(Παράγραφοι 5.8 και 6.1 του [1] και παράγραφοι 10.6 και 10.8 του [3])
Ορίσαμε τα ταιριάσματα και τα πλήρη ταιριάσματα και αναδιατυπώσαμε με γλώσσα γραφημάτων το Θεώρημα του Γάμου. Έπειτα ορίσαμε το μέγιστο ταίριασμα και το επαυξανον μονοπάτι και είδαμε ότι ένα ταίριασμα σε ένα διμερές γράφημα είναι μέγιστο αν και μόνο αν δεν έχει κάποιο επαυξάνον μονοπάτι. Στη συνέχεια είδαμε το θεώρημα König-Egeváry, ορίσαμε τους κύκλους και τα μονοπάτια Euler και Hamilton και είδαμε το θεώρημα του Euler σχετικά με την ύπαρξη ή όχι κύκλου και μονοπατιού Euler σε συνεκτικό γράφημα.
Είδαμε μερικά παραδείγματα σχετικά με κύκλους/μονοπάτια Euler και Hamilton. Επίσης, είδαμε τα θεωρήματα Dirac και Ore. Στην συνέχεια, ορίσαμε την ομομορφία γραφημάτων, ορίσαμε τα επίπεδα γραφήματα και αναφέραμε το θεώρημα των τεσσάρων χρωμάτων και είδαμε σχετικά παραδείγματα. Στη συνέχεια, είδαμε τον τύπο του Euler και με την βοήθειά του δείξαμε ότι τα γραφήματα \(K_5\) και \(K_{3,3}\) δεν είναι επίπεδα. Κλείσαμε με το κριτήριο του Kuratowski.
(Παράγραφος 6.4 του [1] και παράγραφοι 10.7 και 10.8 του [3])
