Θεωρήστε ένα πλήρες γράφημα (οποιεσδήποτε δυό κορυφές συνδέονται με ακμή.) Προσανατολίζουμε τις ακμές του γραφήματος επιτρέποντας την κίνηση ανάμεσα σε δύο κορυφές μόνο κατά τη μια φορά. Δείξτε ότι αν το πλήθος των κορυφών του γραφήματος δεν είναι 2 ή 4 είναι δυνατό να προσανατολίσουμε τις ακμές έτσι ώστε να μπορεί κανείς να πάει από οποιαδήποτε κορυφή σε οποιαδήποτε άλλη περνώντας ενδιάμεσα από μια το πολύ άλλη κορυφή.
Σημείωση: Όποιος λύσει το πρόβλημα “Ικανοποίηση” σίγουρα δεν θα έχει πρόβλημα να λύσει και αυτό το πρόβλημα στην περίπτωση που .
Υπόδειξη:
Αν
είναι προφανές. Αν
δεν είναι τόσο προφανές αλλά δεν είναι και δύσκολο.
Σκεφτείτε επαγωγικά αλλά ξεφύγετε από τα εντελώς συνηθισμένα.
Σχόλιο από Michalis Loulakis — Ιουνίου 2, 2009 @ 12:50 πμ