Διακριτά Μαθηματικά (Μ 2411 ή Μ 251)

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

Τμήμα Μαθηματικών, Πανεπιστήμιο Κρήτης, Λεωφόρος Κνωσού, 714 09 Ηράκλειο, E-mail: kolount AT gmail.com

Φθινόπωρο 2010-11

Περιεχόμενα

• 1 Ωράριο
• 2 Περιγραφή του μαθήματος
  • 2.1 Βιβλίο
  
  
• 3 Βαθμολογικό Σύστημα - Εξετάσεις
• 4 Ημερολόγιο Μαθήματος
  • 4.1 Δε, 20/9/10: Επαγωγή.
  • 4.2 Πέ, 23/9/10: Παραλλαγές επαγωγής
    • 4.2.1 ΑΝΑΚΟΙΝΩΣΗ: Αλλαγή ώρας
  • 4.3 Δε, 27/9/10: Απαρίθμηση και αρχή πολλαπλασιασμού
  • 4.4 Πέ, 30/9/10: Μεταθέσεις συνόλου
    • 4.4.1 ΑΝΑΚΟΙΝΩΣΗ: Ημερομηνίες Διαγωνισμάτων
  • 4.5 Δε, 4/10/10: Συνδυασμοί
  • 4.6 Πέ, 7/10/10: Συνδυασμοί (συνέχεια)
  • 4.7 Δε, 11/10/10: Λύση ασκήσεων
  • 4.8 Πέ, 14/10/10: Συνδυασμοί με επανάθεση
  • 4.9 Δε, 18/10/10: Διάφορες ασκήσεις. Πολυωνυμικοί συντελεστές.
    • 4.9.1 ΑΝΑΚΟΙΝΩΣΗ: Διαγώνισμα Δευτέρας 25/10/2010
  • 4.10 Πέ, 21/10/10: Διωνυμικό Θεώρημα
  • 4.11 Δε, 25/10/10: Πρώτο διαγώνισμα
    • 4.11.1 ΑΝΑΚΟΙΝΩΣΗ: Αποτελέσματα πρώτου διαγωνίσματος
  • 4.12 Πέ, 28/10/10: Αργία, δεν έγινε μάθημα
  • 4.13 Δε, 1/11/10: Εφαρμογές του διωνυμικού θεωρήματος για υπολογισμούς αθροισμάτων
  • 4.14 Πέ, 4/11/10: Συνδυαστικές αποδείξεις ταυτοτήτων
    • 4.14.1 ΑΝΑΚΟΙΝΩΣΗ: Αλλαγή ημερομηνίας 2ου διαγωνίσματος
  • 4.15 Δε, 15/11/10: Εισαγωγή στα Γραφήματα.
  • 4.16 Πέ, 18/11/10: Ισομορφία Γραφημάτων. Συνεκτικότητα.
  • 4.17 Δε, 22/11/10: Απόσταση πάνω σε γραφήματα. Δέντρα.
  • 4.18 Πέ, 25/11/10: Ασκήσεις πάνω σε δέντρα
    • 4.18.1 ΑΝΑΚΟΙΝΩΣΗ: 2ο διαγώνισμα
  • 4.19 Δε, 29/11/10: 2ο Διαγώνισμα
  • 4.20 Πέ, 2/12/10: Λύση ασκήσεων
  • 4.21 Δε, 6/12/10: Ο αλγόριθμος του Kruskal
  • 4.22 Πέ, 9/12/10: Δυνάμεις του πίνακα συνδεσμολογίας και ο αλγόριθμος Floyd-Warshall
  • 4.23 Δε, 13/12/10: Διμερή γραφήματα και ταιριάσματα
  • 4.24 Πέ, 16/12/10: Το θεώρημα του Γάμου
  • 4.25 Δε, 10/1/2011: Θ. König-Egerváry
  • 4.26 Πέ, 13/1/2011: Το Θεώρημα του Γάμου από το Θ. König-Egerváry
    • 4.26.1 Τε, 2/2/2011: Τελική Εξέταση
    • 4.26.2 ΑΝΑΚΟΙΝΩΣΗ: Διαγώνισμα Σεπτεμβρίου

1 Ωράριο

Δευτέρα 5-7, Πέμπτη 9-10 στο Αμφιθέατρο ΣΠ. Έναρξη μαθημάτων: 20/9/10.

Ώρες γραφείου: Τρίτη 10-12 και γενικά μπορείτε να με βρίσκετε τα πρωινά 10-12 στο γραφείο μου (Γ 111, στο προκατασκευασμένο κτήριο της Κνωσού).

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

Από τον οδηγό σπουδών:

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

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

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

Δείτε επίσης την ιστοσελίδα του μαθήματος όπως το δίδαξα το 2008-09.

2.1 Βιβλίο

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

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

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

Θα γίνουν τρία υποχρεωτικά διαγωνίσματα κατά τη διάρκεια του εξαμήνου (συμπεριλαμβανομένου του «τελικού»).

• Για το βαθμό της περιόδου Ιανουαρίου αυτά μετρούν εξ ίσου, το καθένα για το 1/3 του βαθμού.
• Για την περίοδο του Σεπτεμβρίου το 3ο διαγώνισμα του εξαμήνου δε μετράει καθόλου, τα πρώτα δύο μετρούν το καθένα για το 1/6 του βαθμού και το διαγώνισμα του Σεπτεμβρίου μετράει για τα 2/3 του βαθμού.

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

1. Συντρέχουν αντικειμενικοί λόγοι (π.χ. κάποιος υπηρετεί στο στρατό ή μένει μόνιμα αλλού και αδυνατεί να είναι εδώ).
2. Πρέπει κάποιος που επιθυμεί να εξεταστεί μόνο σε τελικό διαγώνισμα να το δηλώσει γραπτώς (email αρκεί) σε μένα μέχρι την Παρασκευή 1 Οκτ, 2010, μαζί με τους λόγους που έχει.

Σε καμιά άλλη περίπτωση δε θα είναι δυνατή εναλλακτική εξέταση.

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

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

Σπανίως θα βγαίνουν ανακοινώσεις που αφορούν το μάθημα σε χαρτί. Παρακαλώ να συμβουλεύεστε αυτή τη σελίδα τουλάχιστον 2-3 φορές την εβδομάδα.

4.1 Δε, 20/9/10: Επαγωγή.

Ορίσαμε τη μέθοδο της μαθηματικής επαγωγής και είδαμε διάφορα παραδείγματα χρήσης της για την απόδειξη προτάσεων που εξαρτώνται από κάποια παράμετρο $n$ που είναι φυσικός αριθμός.

Διαβάστε την §1.1 των σημειώσεων και λύστε τις ασκήσεις που είναι εκεί.

4.2 Πέ, 23/9/10: Παραλλαγές επαγωγής

Σήμερα είδαμε διάφορα παραδείγματα εφαρμογής της μεθόδου της επαγωγής. Είδαμε επίσης και την παραλλαγή «μπρος-πίσω» (δείτε τις σημειώσεις σας) και τη χρησιμοποιήσαμε για να αποδείξουμε την ανισότητα αριθμητικού-γεωμετρικού μέσου.

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

Λύστε όμως όλες τις ασκήσεις που βρίσκονται στις παραγράφους που διαβάζετε και κάντε και το πρότυπο διαγώνισμα που υπάρχει στο τέλος του κεφαλαίου.

4.2.1 ΑΝΑΚΟΙΝΩΣΗ: Αλλαγή ώρας

Από δω και πέρα θα κάνουμε δύο ώρες τη Δευτέρα (5-7 αντί για 5-6) και μια ώρα την Πέμπτη (9-10 αντί για 9-11).

4.3 Δε, 27/9/10: Απαρίθμηση και αρχή πολλαπλασιασμού

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

4.4 Πέ, 30/9/10: Μεταθέσεις συνόλου

Λύσαμε μερικές ασκήσεις από τα προηγούμενα και επίσης είδαμε ότι το πλήθος μεταθέσεων ενός συνόλου με $n$ στοιχεία είναι $n! = 1\cdot 2 \cdot 3 \cdots n$. (Με τόσους τρόπους δηλ. μπορούμε να βάλουμε στη σειρά $n$ διακεκριμένα αντικείμενα.) Λύσαμε και όλες τις ασκήσεις της §2.1.

4.4.1 ΑΝΑΚΟΙΝΩΣΗ: Ημερομηνίες Διαγωνισμάτων

Πρώτο Διαγώνισμα: Δευτέρα 25/10/2010, 7-9μμ, Αμφιθέατρα ΣΠ, ΒΞ.

Δεύτερο Διαγώνισμα: Δευτέρα 29/11/2010, 7-9μμ, Αμφιθέατρα ΣΠ, ΒΞ.

4.5 Δε, 4/10/10: Συνδυασμοί

Σήμερα είδαμε ότι αν θέλουμε νε επιλέξουμε $k$ αντικείμενα από $n$ διαφορετικά αντικείμενα, χωρίς να μας ενδιαφέρει η σειρά της επιλογής, τότε αυτό μπορεί να γίνει με

$${n \choose k} = \frac{n(n-1)\cdots(n-k+1)}{k!} = \frac{n!}{k!(n-k)!}$$

διαφορετικούς τρόπους.

Είδαμε επίσης διάφορα παραδείγματα και ασκήσεις σχετικές με αυτό. Διαβάστε το υπόλοιπο του Κεφ. 2.

4.6 Πέ, 7/10/10: Συνδυασμοί (συνέχεια)

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

Παρακαλώ πολύ να κοιτάξετε να λύσετε όλες τις ασκήσεις που υπάρχουν στις σημειώσεις σας.

4.7 Δε, 11/10/10: Λύση ασκήσεων

Σήμερα λύσαμε διάφορες ασκήσεις. Αυτές έχουν προστεθεί στις σημειώσεις σας (με μπλε χρώμα) στο τέλος του Κεφ. 2.

4.8 Πέ, 14/10/10: Συνδυασμοί με επανάθεση

Σήμερα είδαμε το κεντρικό αποτέλεσμα της παραγράφου §3.1, ένα τύπο δηλ. που μας λέει με πόσους τρόπους μπορούμε να επιλέξουμε $k$ αντικείμενα από $n$ διαφορετικά αντικείμενα, όταν κάθε αντικείμενο μπορεί να επιλεγεί και παραπάνω από 1 φορά. Ο τύπος είναι

$${n+k-1 \choose k}.$$

4.9 Δε, 18/10/10: Διάφορες ασκήσεις. Πολυωνυμικοί συντελεστές.

Λύσαμε διάφορες ασκήσεις και ορίσαμε τους πολυωνυμικούς (συντελεστές)

$${n \choose k_1, k_2, \ldots, k_m},$$

όπου $k_1+\cdots+k_m = n$, που μετράνε με πόσους τρόπους μπορούμε να διαμερίσουμε το σύνολο $[n]={\left\{{1,2,\ldots,n}\right\}}$ σε $m$ υποσύνολα $A_1,\ldots,A_m$ τ.ώ, ${\left\vert{A_j}\right\vert}=k_j$.

Αποδείξαμε ότι

$${n \choose k_1, k_2, \ldots, k_m} = \frac{n!}{k_1! k_2! \cdots k_m!}.$$

4.9.1 ΑΝΑΚΟΙΝΩΣΗ: Διαγώνισμα Δευτέρας 25/10/2010

Το πρώτο διαγώνισμα του εξαμήνου θα γίνει την Δευτέρα 25/10/10 και ώρες 19:00-21:00. Την ίδια μέρα δε θα γίνει το μάθημα από 17:00 έως 19:00.

Η εξεταστέα ύλη θα αποτελείται από οτιδήποτε έχουμε καλύψει ως και την Πέμπτη 21/10/10.

Θα αποτελείται από δύο μέρη. Ένα μέρος με ερωτήσεις πολλαπλής επιλογής και ένα μέρος συμβατικού τύπου (με ερωτήσεις δηλ. στις οποίες θα πρέπει να απαντήσετε αναλυτικά).

Μπορείτε να δείτε εδώ σε μορφή PDF ένα παλιό διαγώνισμα πολλαπλών επιλογών ώστε να ξέρετε περίπου τι να περιμένετε.

Θα υπάρξει ενδιάμεσο διάλλειμα.

Παρακαλώ πολύ να έχετε μαζί σας ταυτότητα (αστυνομική, πάσο, δίπλωμα οδήγησης, ...).

4.10 Πέ, 21/10/10: Διωνυμικό Θεώρημα

Είδαμε μερικά παραδείγματα χρήσης των πολυωνυμικών συντελεστών και αποδείξαμε το διωνυμικό θεώρημα (με επαγωγή και με συνδυαστικό επιχείρημα):

$$(a+b)^n = \sum_{k=0}^n {n \choose k} a^k b^{n-k}.$$

Το χρησιμοποιήσαμε για να δείξουμε τις ταυτότητες

$$2^n = \sum_{k=0}^n {n \choose k}$$

και

$$\sum_{0\le k \le n \atop \mbox{$k=2\ell+1$}} {n \choose k} = \sum_{0\le k \le n \atop \mbox{$k=2\ell$}} {n \choose k},$$

(με επιλογή $a=b=1$ και $a=-b=1$ αντίστοιχα).

4.11 Δε, 25/10/10: Πρώτο διαγώνισμα

Σήμερα είχαμε το πρώτο μας διαγώνισμα που απαρτιζόταν από

• το πρώτο μέρος (ερωτήματα πολλαπλών επιλογών, λύσεις εδώ σε μορφή PDF για ένα τυπικό τέτοιο διαγώνισμα) και
• το δεύτερο μέρος (συμβατικό διαγώνισμα) το οποίο (2ο μέρος) μπορείτε να βρείτε εδώ σε μορφή PDF μαζί με τις λύσεις.

4.11.1 ΑΝΑΚΟΙΝΩΣΗ: Αποτελέσματα πρώτου διαγωνίσματος

Μπορείτε να τα δείτε εδώ.

Ο συνολικός βαθμός του 1ου διαγωνίσματος είναι κατά το ήμισυ ο βαθμός από το διαγώνισμα πολλαπλών επιλογών και κατά το ήμισυ από το συμβατικό διαγώνισμα.

4.12 Πέ, 28/10/10: Αργία, δεν έγινε μάθημα

4.13 Δε, 1/11/10: Εφαρμογές του διωνυμικού θεωρήματος για υπολογισμούς αθροισμάτων

Είδαμε διάφορες εφαρμογές του διωνυμικού θεωρήματος στον υπολογισμό αθροισμάτων όπως τα $\sum_{k=0}^n k{n \choose k}$ ή $\sum_{k=0}^n k^2{n \choose k}$.

Στις σημειώσεις στην §3.3 θα βρείτε το πώς μπορούμε να υπολογίσουμε το άθροισμα

$$\sum_{k=0}^n \frac{1}{k+1} {n \choose k}$$

ουσιαστικά ολοκληρώνοντας το διωνυμικό θεώρημα στη μορφή $(1+x)^n=\sum_{k=0}^n {n \choose k} x^k$. Στο μάθημα προσπάθησα να βγάλω το εντελώς παρόμοιο άθροισμα

$$\sum_{k=1}^n \frac{1}{k} {n \choose k}$$

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

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

4.14 Πέ, 4/11/10: Συνδυαστικές αποδείξεις ταυτοτήτων

Σήμερα είδαμε διάφορες τεχνικές με τις οποίες μπορεί κανείς να αποδείξει κάποιες ταυτότητες, όπως η

$$2^n = \sum_{k=0}^n {n \choose k}$$

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

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

4.14.1 ΑΝΑΚΟΙΝΩΣΗ: Αλλαγή ημερομηνίας 2ου διαγωνίσματος

Το 2ο διαγώνισμα μετατίθεται για μια εβδομάδα μετά λόγω της εβδομάδας που χάσαμε για τις εκλογές.

4.15 Δε, 15/11/10: Εισαγωγή στα Γραφήματα.

Αφού λύσαμε μερικές ακόμη ασκήσεις από την τελευταία παράγραφο του Κεφ. 3 (συνδυαστικές αποδείξεις ταυτοτήτων) κάναμε μια μικρή εισαγωγή στις βασικές έννοιες της θεωρίας γραφημάτων.

4.16 Πέ, 18/11/10: Ισομορφία Γραφημάτων. Συνεκτικότητα.

Ορίσαμε την έννοια των ισόμορφων γραφημάτων και είδαμε διάφορα παραδείγματα.

Μιλήσαμε για μονοπάτια πάνω σε γραφήματα και ορίσαμε τις συνεκτικές συνιστώσες ενός γραφήματος.

4.17 Δε, 22/11/10: Απόσταση πάνω σε γραφήματα. Δέντρα.

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

Ορίσαμε τι είναι ένα δέντρο (συνεκτικό γράφημα χωρίς κύκλους) και διάφορες ιδιότητες των δέντρων (κάθε δέντρο με $n$ κορυφές έχει $n-1$ ακμές, για παράδειγμα).

4.18 Πέ, 25/11/10: Ασκήσεις πάνω σε δέντρα

Λύσαμε διάφορες ασκήσεις σχετικές με δέντρα.

4.18.1 ΑΝΑΚΟΙΝΩΣΗ: 2ο διαγώνισμα

Το 2ο διαγώνισμα θα γίνει την Δευτέρα 29/11/10 στο Αμφ. ΒΞ, 7-9μμ, και θα έχει την ίδια μορφή με το προηγούμενο. Και πάλι δε θα γίνει το μάθημα 5-7 εκείνη τη μέρα.

4.19 Δε, 29/11/10: 2ο Διαγώνισμα

Σήμερα είχαμε το 2ο διαγώνισμα. Μπορείτε να δείτε τους βαθμούς σας εδώ.

Το διαγώνισμα αποτελούνταν από δύο μέρη: το πρώτο μέρος (ερωτήματα πολλαπλών επιλογών, λύσεις εδώ σε μορφή PDF για ένα τυπικό τέτοιο διαγώνισμα) και το δεύτερο (συμβατικό διαγώνισμα) που μπορείτε να δείτε εδώ σε μορφή PDF μαζί με τις λύσεις.

4.20 Πέ, 2/12/10: Λύση ασκήσεων

Σήμερα είδαμε τις λύσεις των ασκήσεων που μπήκαν στο 2ο διαγώνισμα.

4.21 Δε, 6/12/10: Ο αλγόριθμος του Kruskal

Είδαμε τον αλγόριθμο του Kruskal για εύρεση ενός ελάχιστου δέντρου σε ένα απλό γράφημα με βάρη στις ακμές του. Ελάχιστο καλείται ένα δέντρο που παράγει το γράφημα («πάει» σε όλες τις κορυφές του) αν το άθροισμα των βαρών των ακμών που συμμετέχουν σ' αυτό.

Επίσης αποδείξαμε ότι ο αλγόριθμος όντως βρίσκει ένα τέτοιο δέντρο.

4.22 Πέ, 9/12/10: Δυνάμεις του πίνακα συνδεσμολογίας και ο αλγόριθμος Floyd-Warshall

Αποδείξαμε ότι το στοιχείο $(A^k)_{ij}$ ($k$ δύναμη του πίνακα συνδεσμολογίας $A$ ενός γραφήματος $G$) παριστάνει το πλήθος των μονοπατιών από την κορυφή $i$ στην κορυφή $j$ με μήκος $k$.

Έπειτα είδαμε τον αλγόριθμο Floyd-Warshall, ο οποίος υπολογίζει για ένα γράφημα $G$ με μήκη (βάρη) στις ακμές του την απόσταση ανάμεσα στις κορυφές $i$ και $j$ για κάθε ζεύγος κορυφών. Αποδείξαμε ότι ο αλγόριθμος όντως υπολογίζει αυτό που ισχυριστήκαμε.

4.23 Δε, 13/12/10: Διμερή γραφήματα και ταιριάσματα

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

4.24 Πέ, 16/12/10: Το θεώρημα του Γάμου

Αποδείξαμε το θεώρημα του Γάμου (η απόδειξη βρίσκεται στο πρώτο Κεφάλαιο των σημειώσεων) και το διατυπώσαμε και με τη γλώσσα των πλήρων ταιριασμάτων σε διμερή γραφήματα.

4.25 Δε, 10/1/2011: Θ. König-Egerváry

Αποδείξαμε ότι ένα τάιριασμα ακμών σε ένα διμερές γράφημα είναι μέγιστο αν και μόνο αν δεν υπάρχουν επαυξάνοντα μονοπάτια στο γράφημα και το χρησιμοποιήσαμε για να δείξουμε το Θεώρημα König-Egerváry, που λέει ότι σ' ένα διμερές γράφημα το μέγεθος του μέγιστου ταιριάσματος ακμών ισούται με το μέγεθος του ελάχιστου καλύμματος κορυφών (ένα σύνολο κορυφών λέγεται κάλυμμα αν κάθε ακμή περιέχει μια κορυφή από αυτό το σύνολο).

4.26 Πέ, 13/1/2011: Το Θεώρημα του Γάμου από το Θ. König-Egerváry

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

4.26.1 Τε, 2/2/2011: Τελική Εξέταση

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

Οι βαθμοί είναι εδώ.

4.26.2 ΑΝΑΚΟΙΝΩΣΗ: Διαγώνισμα Σεπτεμβρίου

Το διαγώνισμα Σεπτεμβρίου θα γίνει στις 15/9/2011, 17:00-20:00 στις αίθουσες ΡΑ101, ΡΑ201. Θα εξετεαστείτε σε όλη την ύλη που διδάχτηκε κατά τη διάρκεια του εξαμήνου.

Οι βαθμοί είναι εδώ (τελικοί μόνο, pdf) και εδώ αναλυτικά.