Διακριτά: Θεωρία Γραφημάτων

Περιεχόμενα

Κεφ. 1 · Βασικές έννοιες11 ενότητες

• 1.1 Τι είναι ένα γράφημα
• 1.2 Απλά γραφήματα
• 1.3 Οι «διάσημοι»: κλίκα και κύκλος
• 1.4 Περίπατοι, μονοπάτια, κύκλοι
• 1.5 Υπογράφημα και επαγόμενο υπογράφημα
• 1.6 Το συμπλήρωμα ενός γραφήματος
• 1.7 Συνεκτικά γραφήματα
• 1.8 Γέφυρες και σημεία κοπής
• 1.9 Λυμένες ασκήσεις
• 1.10 Δίπλα-δίπλα
• 1.11 Έλεγξε τι κατάλαβες

Κεφ. 2 · Βαθμοί κορυφών και Λήμμα Χειραψίας7 ενότητες

• 2.1 Ο βαθμός μιας κορυφής
• 2.2 Το Λήμμα Χειραψίας
• 2.3 Γραφικές ακολουθίες
• 2.4 Κανονικά γραφήματα
• 2.5 Περισσότερες λυμένες ασκήσεις
• 2.6 Δίπλα-δίπλα
• 2.7 Έλεγξε τι κατάλαβες

Κεφ. 3 · Διμερή γραφήματα, ανεξάρτητα σύνολα, χρωματισμοί6 ενότητες

• 3.1 Διμερή γραφήματα
• 3.2 Ανεξάρτητα σύνολα
• 3.3 Χρωματισμοί
• 3.4 Ασκήσεις τύπου θέμα
• 3.5 Δίπλα-δίπλα
• 3.6 Έλεγξε τι κατάλαβες

Κεφ. 4 · Κύκλοι και μονοπάτια Euler5 ενότητες

• 4.1 Ο κύκλος Euler
• 4.2 Ποια διάσημα γραφήματα έχουν κύκλο Euler
• 4.3 Το μονοπάτι Euler
• 4.4 Δίπλα-δίπλα
• 4.5 Έλεγξε τι κατάλαβες

Κεφ. 5 · Κύκλοι Hamilton5 ενότητες

• 5.1 Ο κύκλος Hamilton
• 5.2 Δύο ικανές συνθήκες: Dirac και Ore
• 5.3 Λυμένες ασκήσεις
• 5.4 Δίπλα-δίπλα
• 5.5 Έλεγξε τι κατάλαβες

Κεφ. 6 · Επίπεδα γραφήματα7 ενότητες

• 6.1 Επίπεδα γραφήματα
• 6.2 Όψεις και ο τύπος του Euler
• 6.3 Οι δύο «κόφτες» των επίπεδων γραφημάτων
• 6.4 Λυμένες ασκήσεις
• 6.5 Ομοιομορφικά γραφήματα και θεώρημα Kuratowski
• 6.6 Δίπλα-δίπλα
• 6.7 Έλεγξε τι κατάλαβες

Κεφ. 7 · Αναπαράσταση γραφημάτων και ισομορφισμοί7 ενότητες

• 7.1 Πίνακας γειτνίασης
• 7.2 Πίνακας πρόσπτωσης
• 7.3 Δυνάμεις του πίνακα γειτνίασης
• 7.4 Ισομορφικά γραφήματα
• 7.5 Αυτοσυμπληρωματικά γραφήματα
• 7.6 Δίπλα-δίπλα
• 7.7 Έλεγξε τι κατάλαβες

Κεφ. 8 · Δέντρα7 ενότητες

• 8.1 Δέντρα: ορισμός και ιδιότητες
• 8.2 Οι 8 προτάσεις για τα δέντρα
• 8.3 Λυμένες ασκήσεις
• 8.4 Η ακολουθία Prüfer
• 8.5 Ριζωμένα και δυαδικά δέντρα
• 8.6 Δίπλα-δίπλα
• 8.7 Έλεγξε τι κατάλαβες

Κεφ. 9 · Μαθηματική επαγωγή στα γραφήματα7 ενότητες

• 9.1 Πώς δουλεύει η μαθηματική επαγωγή
• 9.2 Επαγωγή σε γραφήματα: αφαιρώ και ξαναβάζω
• 9.3 Λυμένες ασκήσεις
• 9.4 Τουρνουά
• 9.5 Δέντρα μέσα σε συμπληρώματα κύκλων
• 9.6 Δίπλα-δίπλα
• 9.7 Έλεγξε τι κατάλαβες

Κεφ. 10 · Ταιριάσματα, καλύμματα και κατασκευές γραφημάτων9 ενότητες

• 10.1 Ταιριάσματα
• 10.2 Καλύμματα κορυφών
• 10.3 Χρωματισμός ακμών
• 10.4 Γραμμική διάταξη
• 10.5 Το γραμμογράφημα
• 10.6 Πράξεις με γραφήματα
• 10.7 Κάθε γράφημα «ζει» μέσα σε ένα κανονικό
• 10.8 Δίπλα-δίπλα
• 10.9 Έλεγξε τι κατάλαβες

Κεφ. 11 · Γραφήματα και κατηγορηματική λογική3 ενότητες

• 11.1 Η γλώσσα των γραφημάτων
• 11.2 Ασκήσεις τύπου θέμα
• 11.3 Έλεγξε τι κατάλαβες

Κεφ. 12 · Αποστάσεις, διάμετρος, κέντρο και συνεκτικότητα7 ενότητες

• 12.1 Απόσταση, εκκεντρότητα, διάμετρος
• 12.2 Λυμένες ασκήσεις: διάμετρος και κέντρο
• 12.3 Αποδείξεις με μονοπάτια
• 12.4 Συνεκτικότητα κορυφών και ακμών
• 12.5 Λυμένες ασκήσεις: συνεκτικότητα
• 12.6 Δίπλα-δίπλα
• 12.7 Έλεγξε τι κατάλαβες