Θεωρία Γραφημάτων 1

[Demetres]

Ο Γιώργος ισχυρίζεται ότι χθες βρισκόταν σε μια συνάντηση με άλλα εννιά άτομα οι οποίοι (συμπεριλαμβανομένου του Γιώργου) έκαναν 3,4,4,4,5,5,6,6,7,7 χειραψίες αντίστοιχα.

Ο Ανδρέας είναι σίγουρος πως ο Γιώργος έχει κάνει λάθος στο μέτρημα. Πως το ξέρει;

[Marios V.]

Οι χειραψίες γίνονται σε "ζευγάρια".(αν ο x κάνει χειραψία με με τον y τότε αυτόματα έχει κάνει και ο y me ton x).
άρα συνολικά ζητάμε άρτιο αριθμό χειραψιών, κάτι που δεν ισχύει στην δική μας περίπτωση.

[Demetres]

Ωραία. Να αναφέρω σχετικά με τον τίτλο ότι μπορούμε να παραστήσουμε αυτήν την κατάσταση με ένα "γράφημα" το οποίο αποτελείται από 10 σημεία τα οποία ονομάζουμε κορυφές (μια κορυφή για κάθε άτομο) και στο οποίο ενώνουμε δυο κορυφές μεταξύ τους με μια γραμμή την οποία ονομάζουμε ακμή αν και μόνο αν τα αντίστοιχα άτομα έχουν κάνει χειραψία μεταξύ τους.

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

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