Διακριτά Μαθηματικά Ι

Μιχάλης Κολουντζάκης

Τμήμα Μαθηματικών
Πανεπιστήμιο Κρήτης
Λεωφόρος Κνωσού
714 09 Ηράκλειο

E-mail: kolount AT member.ams.org

Φθινόπωρο 2003-04

1 Ωράριο

Το μάθημα γίνεται σε δύο Τμήματα-παρακολουθείστε όποιο σας βολεύει:

• Τρίτη 11-2, Αμφιθέατρο Βασ. Ξανθόπουλου.
• Τρίτη 2-5, Αμφιθέατρο Βασ. Ξανθόπουλου.

Ώρες γραφείου: Τετάρτη 11-1

2 Βαθμολογικό Σύστημα - Εξετάσεις

Δε θα υπάρξει πρόοδος. Θα βαθμολογηθείτε μόνο με τον τελικό.

3 Περιγραφή του μαθήματος

Από τον οδηγό σπουδών του Τμήματος:

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

Περιεχόμενο:

1. Στοιχεία θεωρίας συνόλων, απεικονίσεις, επαγωγή, αλγόριθμοι, αναδρομικές σχέσεις.
2. Bασικές αρχές συνδυαστικής, διατάξεις, συνδυασμοί, συνδυαστικές ταυτότητες, προβλήματα αντιστοίχισης.
3. Γραφήματα, μονοπάτια, κυκλώματα - ιδιότητες και εφαρμογές.
4. Eίδη δένδρου - ιδιότητες και εφαρμογές, μοντέλα δικτύων.
5. Αλγεβρες Boole, προτασιακός λογισμός.

Μπορείτε επίσης εδώ να δείτε τη σελίδα του μαθήματος όπως διδάχτηκε την άνοιξη 1997-98 και εδώ όπως διδάχτηκε το φθινόπωρο του 2002-03.

4 Διδακτικές σημειώσεις

Θα γράφονται σημειώσεις κατά τη διάρκεια του εξαμήνου και θα διανέμονται κατ' αρχήν από αυτήν εδώ την ιστοσελίδα.

Ανά πάσα στιγμή θα μπορείτε να βρίσκετε εδώ την τελευταία μορφή των σημειώσεων σε

• μορφή Postscript και σε
• μορφή PDF.

Ημερομηνία τελευταίας ενημέρωσης: 20 Ιαν. 2004 (περιλαμβάνει μέχρι και το Κεφ. 5, και δε θα δοθούν άλλες σημειώσεις).

Να έχετε υπόψιν ότι αλλαγές θα γίνονται καθ' όλη τη διάρκεια του εξαμήνου, και όχι κατ' ανάγκη στα τελευταία κομμάτια.

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

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

Αν ανακαλύψετε τυχόν λάθη ή έχετε κάποιες άλλες παρατηρήσεις να κάνετε παρακαλώ στείλτε μου e-mail.

5 Ημερολόγιο μαθήματος

5.1 Τρ, 7/10/03: Επαγωγή

Κάναμε όλο το Κεφ. 1 των σημειώσεων (Επαγωγή) εκτός τις παραγράφους 2.1 και 3.

5.2 Τρ, 14/10/03: Βασικές αρχές απαρίθμησης

Καλύψαμε την παράγραφο 1 του Κεφ. 2. Λύστε όλες τις ασκήσεις που βρίσκονται εκεί.

5.3 Τρ, 21/10/03: Βασικές αρχές απαρίθμησης, Μέρος ΙΙ

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

5.3.1 Τε, 29/10/03: ΑΝΑΚΟΙΝΩΣΗ

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

5.4 Τρ, 4/11/03: Προχωρημένη Απαρίθμηση

Καλύψαμε το Κεφ. 3 των σημειώσεων.

5.4.1 Τρ, 4/11/03: ΑΝΑΚΟΙΝΩΣΗ

Τις εβδομάδες της 10ης και 17ης Νοεμβρίου 2003 δε θα γίνει το μάθημα των Διακριτών Μαθ. Ι (στις 11/11 λόγω της αργίας του Αγ. Μηνά και στις 18/11 λόγω απουσίας δικιάς μου).

5.5 Τρ, 25/11/03: Εισαγωγή στη Θεωρία Γραφημάτων

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

5.5.1 Τρ, 2/12/03: Φυλλάδιο ασκήσεων

Μπορείτε να βρείτε σε μορφή Postscript ή PDF ένα φυλλάδιο με συγκεντρωμένες ασκήσεις τις οποίες καλό θα είναι να λύσετε ως προετοιμασία για την τελική εξέταση του μαθήματος. Θα πρέπει να τις επιστρέψετε λυμένες μέχρι την Τρίτη 16 Δεκεμβρίου 2003, ώστε να μπορέσουν οι βοηθοί του μαθήματος να τις διορθώσουν στη διάρκεια των Χριστουγέννων. Δε θα έχουν άμεση βαθμολογική επίπτωση.

5.6 Τρ, 2/12/2003: Εισαγωγή στη Θεωρία Γραφημάτων, II

Καλύψαμε μέχρι και την παράγραφο 4.5.

Μια διευκρίνιση όσον αφορά τη μοναδικότητα των διαδρομών στα δέντρα (Άσκηση 4.28, που χρησιμοποιείται και στην Άσκηση 4.26).

Ορισμός 1   Διαδρομή σε ένα απλό γράφημα είναι ένα μονοπάτι που δεν χρησιμοποιεί καμιά ακμή παραπάνω από μία φορά.

Θεώρημα 1   Αν $\pi_1$ και $\pi_2$ είναι δύο διαδρομές σε ένα δέντρο $T$ που συνδέουν μεταξύ τους τις κορυφές $u$ και $v$, τότε $\pi_1 = \pi_2$.

Proof. Έστω ότι

$$\pi_1 = a_0, a_1, \ldots, a_k$$

και

$$\pi_2 = b_0, b_1, \ldots, b_l$$

με

$$a_0 = b_0 = u, a_k = b_l = v$$

είναι δύο διαδρομές από το $u$ στο $v$.

Υποθέτουμε ότι οι δύο διαδρομές είναι διαφορετικές και δείχνουμε ότι υπάρχει κύκλος στο γράφημα $T$, πράγμα αδύνατο μια και είναι δέντρο.

Έστω $A$ το σύνολο των κορυφών που εμαφανίζονται στο $\pi_1$ και στο $\pi_2$ (το σύνολο των κοινών κορυφών).

Θέτουμε $i=0$ και αυξάνουμε το $i$ κατά ένα έως ότου $a_i \neq b_i$. (Αυτό σίγουρα θα συμβεί κάποτε μια και $\pi_1 \neq \pi_2$.)

Θέτουμε $j=i$ και αυξάνουμε το $j$ κατά ένα έως ότου $a_j \in A$. (Και αυτό σίγουρα θα συμβεί κάποτε μια και σίγουρα $a_k \in A$.) Εφ όσον $a_j \in A$ τότε υπάρχει $r$ τέτοιο ώστε $a_j = b_r$. Ισχυριζόμαστε τώρα ότι το κύκλωμα

$$\pi = a_{i-1}, a_i, a_{i+1}, \ldots, a_j, b_{r-1}, b_{r-2}, \ldots, b_{i-1}=a_{i-1}$$

είναι κύκλος, δεν χρησιμοποιείται δηλ. καμιά του ακμή δύο φορές.

Επειδή τα κομμάτια του $\pi$ (των οποίων η ένωση κάνει το $\pi$)

$$\pi_1' = a_{i-1}, a_i, a_{i+1}, \ldots, a_j$$

και

$$\pi_2' = a_j, b_{r-1}, b_{r-2}, \ldots, b_{i-1}$$

είναι τμήματα διαδρομών (των $\pi_1$ και $\pi_2$) σίγουρα δεν επαναλαμβάνουν ακμές εσωτερικά. Άρα το μόνο που έχουμε να ελέγξουμε είναι αν κάποια ακμή του $\pi_1'$ συμπίπτει με κάποια ακμή του $\pi_2'$.

Όμως οι κορυφές $a_i,\ldots,a_{j-1}$ του $\pi_1'$ δεν εμφανίζονται (εξ επιλογής του $a_j$) στο $\pi_2$ άρα δεν υπάρχουν κοινές ακμές μια και όλες οι ακμές του $\pi_1'$ χρησιμοποιούν τουλάχιστον μια κορυφή που δεν εμφανίζεται στο $\pi_2$. $\qedsymbol$

5.6.1 Πα, 12/12/03: ΑΝΑΚΟΙΝΩΣΗ

Την Τρίτη 16 Δεκ. 2003 δε θα πραγματοποιηθεί το δεύτερο τρίωρο (2-5) του μαθήματος λόγω γενικής συνέλευσης των φοιτητών του Τμήματος Μαθηματικών. Παρακαλούνται όσοι είχαν σκοπό να παρακολουθήσουν αυτό το τρίωρο να έρθουν στο πρώτο (11-2).

5.6.2 Δε, 15/12/03: ΑΝΑΚΟΙΝΩΣΗ

Αγνοείστε την Άσκηση 4.31 των σημειώσεων (που δίνει μια ισοδύναμη συνθήκη για το πότε ένα γράφημα είναι διπλά συνεκτικό). Εκ παραδρομής, στην άσκηση 4.30 έδωσα λάθος ορισμό για το τι είναι διπλά συνεκτικό γράφημα. Η 4.30 δεν επηρεάζεται.

5.7 Τρ, 16/12/03: Εισαγωγή στη Θ. Γραφημάτων, ΙΙΙ

Είδαμε τους αλγορίθμους Floyd-Warshall και Kruskal για εύρεση ελάχιστων μονοπατιών σε γραφήματα με βάρη.

5.8 Τρ, 13/1/04: Διμερή Γραφματα και ταιριάσματα, Ι

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

5.9 Τρ, 20/1/04: Διμερή Γραφματα και ταιριάσματα, ΙΙ

Είδαμε κριτήρια για το πότε ένα ταίριασμα σε ένα διμερές γράφημα είναι μέγιστο. Το κυριότερο θεώρημα είναι αυτό των König και Egerváry, που μπορεί επίσης να μας δώσει και μια εναλλακτική απόδειξη του θεωρήματος του Hall.

5.9.1 Πα, 2/1/04: Φυλλάδιο ασκήσεων: λύσεις

Μπορείτε να βρείτε σε μορφή Postscript ή PDF λύσεις για το φυλλάδιο ασκήσεων από το βοηθό του μαθήματος Γιώργο Αραμπατζή.

6 ΤΕΛΙΚΟΙ ΒΑΘΜΟΙ ΦΕΒΡΟΥΑΡΙΟΥ

Μπορείτε να βρείτε τους τελικούς βαθμούς εδώ με αύξουσα σειρά Α.Μ. και εδώ με φθίνουσα σειρά βαθμού.

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

7 ΤΕΛΙΚΟΙ ΒΑΘΜΟΙ ΣΕΠΤΕΜΒΡΙΟΥ

Εδώ.