Προβλήματα Μαθηματικών

Απριλίου 25, 2009

Μονόδρομοι

Κατηγορίες: Άλυτα Προβλήματα, Με υπόδειξη — Michalis Loulakis @ 3:37 πμ

Θεωρήστε ένα πλήρες γράφημα (οποιεσδήποτε δυό κορυφές συνδέονται με ακμή.) Προσανατολίζουμε τις ακμές του γραφήματος επιτρέποντας την κίνηση ανάμεσα σε δύο κορυφές μόνο κατά τη μια φορά. Δείξτε ότι αν το πλήθος των κορυφών του γραφήματος n δεν είναι 2 ή 4 είναι δυνατό να προσανατολίσουμε τις ακμές έτσι ώστε να μπορεί κανείς να πάει από οποιαδήποτε κορυφή σε οποιαδήποτε άλλη περνώντας ενδιάμεσα από μια το πολύ άλλη κορυφή.

Σημείωση: Όποιος λύσει το πρόβλημα “Ικανοποίηση” σίγουρα δεν θα έχει πρόβλημα να λύσει και αυτό το πρόβλημα στην περίπτωση που n>20.

1 σχόλιο »

  1. Υπόδειξη:

    Αν n=3 είναι προφανές. Αν n=6 δεν είναι τόσο προφανές αλλά δεν είναι και δύσκολο.
    Σκεφτείτε επαγωγικά αλλά ξεφύγετε από τα εντελώς συνηθισμένα.

    Σχόλιο από Michalis Loulakis — Ιουνίου 2, 2009 @ 12:50 πμ


Κανάλι RSS για τα σχόλια του άρθρου. TrackBack URI

Γράψτε ένα σχόλιο

Για να σχολιάσετε πρέπει να συνδεθείτε.

Blog στο WordPress.com.