Μάθημα : Θεωρία Γραφημάτων

Καλημέρα σε όλα,

Οι βαθμοί της εξεταστικής εαρινού εξαμήνου 2025 αναρτήθηκαν στα έγγραφα. Παρακαλώ δώστε προσοχή στα παρακάτω, πριν μου γράψετε e-mail:

1) Οι μη ακέραιοι βαθμοί στρογγυλοποιούνται προς τα πάνω. Οι βαθμοί >10 γίνονται 10.

2) e-mail δέχομαι μόνο  στην διεύθυνση jlivier89@math.uoa.gr και αρκεί μόνο ένα. Πιθανότατα δεν θα απαντήσω πριν το ΣΚ.

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

4) Ένα γράφημα δεν χρειάζεται να έχει κύκλο για να έχει χρωματικό αριθμό μεγαλύτερο ή ίσο του 2. Αρκεί να έχει μια ακμή.

5) Ένας κύκλος δεν έχει αρθρικές κορυφές. Όμως, ένας κύκλος που είναι υπογράφημα ενός γραφήματος φυσικά και μπορεί να έχει αρθρικές κορυφές: πάρτε ως γράφημα έναν κύκλο C οποιουδήποτε μήκους, μία κορυφή u εκτός του C και την ακμή {u,v}, όπου v κάποια από τις κορυφές του C. Η v είναι αρθρική.

6) Έστω ένα γράφημα G και δύο k-χρωματίσιμα υπογραφήματά του Α,Β. Το ότι τα Α,Β είναι k-χρωματίσιμα από μόνο του δεν μας εξασφαλίζει ότι αρκούν k-χρώματα για να βαφτούν ορθά τα Α,Β ταυτόχρονα, πόσο μάλλον ολόκληρο το γράφημα. Θέλει επιχειρήματα (απόδειξη) που να αφορούν την δομή του γραφήματος ή αλγόριθμο που να εξηγεί πως k-χρωματίζουμε σωστά το γράφημα, όταν αυτό είναι δυνατό. 

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

8) Παρ'ότι τα φύλλα, τα δέντρα και τα δάση είναι όροι της Θεωρίας Γραφημάτων, δεν "φυτρώνουν" πουθενά, ούτε πάνω σε κύκλους, ούτε αλλού. Τα "εκβλαστώματα" και λοιπά αντίστοιχα πράγματα που διάβασα, είναι μάλλον σε μαθήματα που αφορούν βιολογία κτλ, σίγουρα πάντως όχι στο παρών.

Γ. Λ.