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

Απρίλιος 25, 2009

Μονόδρομοι

Filed under: Λυμένα Προβλήματα — Michalis Loulakis @ 3:37 πμ

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

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

Advertisements

10 Σχόλια »

  1. Υπόδειξη:

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

    Μου αρέσει!

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

  2. Υπόδειξη:
    Δείξτε ότι αν ο ισχυρισμός είναι αληθής για n=k τότε είναι αληθής και για n=k+2.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Μαρτίου 11, 2010 @ 5:48 μμ

  3. Νομίζω πως το παρακάτω επιχείρημα αποδεικνύει το ζητούμενο για ‘μεγάλα’ n.

    Ας ονομάσουμε τη ζητούμενη συνθήκη, συνθήκη Σ.
    Υποθέστε ότι αποφασίζουμε για τον προσανατολισμό κάθε ακμής ρίχνοντας ένα τίμιο νόμισμα.
    Σταθεροποιείστε ένα ζεύγος κορυφών v,w . Τότε η πιθανότητα να μπορούμε
    να πάμε από την v στην w σε ένα βήμα αλλά να μή μπορούμε να πάμε από την w στη v
    σε 2 βήματα ισουται με \frac{1}{2}(\frac{3}{4})^{n-2} .
    Συνεπώς ο μέσος αριθμός, \mathbb{E}_n από ζεύγη κορυφών του γραφήματος
    για τα οποία η Σ δεν ισχύει ισουται με
    \displaystyle \binom{n}{2} (\frac{3}{4})^{n-2} \rightarrow 0 του n \rightarrow \infty.
    Συνεπώς αν n είναι τέτοιο ώστε  latex \mathbb{E}_n < 1 $ έπεται πως υπάρχει
    προσανατολισμός ώστε το πλήθος των ζευγών που δεν ικανοποιούν τη Σ να είναι < \mathbb{E}_n < 1 ,
    δηλαδή μηδέν.

    Μου αρέσει!

    Σχόλιο από henk&christos — Μαρτίου 8, 2012 @ 6:48 μμ

  4. Να προτείνω μια άλλη λύση χρησιμοποιώντας την υπόδειξη.

    Έστω ότι ο ισχυρισμός είναι σωστός για n=k . Θα δείξουμε ότι είναι σωστός για n=k+2. Έστω G το πλήρες γράφημα με k+2 κορυφές, τις \{v_1,v_2,\ldots,v_k,u,w\} . Επιλέγουμε ένα προσανατολισμό για το υπογράφημα του G με κορυφές \{v_1,v_2,\ldots,v_k\} (που είναι πλήρες γράφημα με k κορυφές) έτσι ώστε να ικανοποιεί τον ισχυρισμό. Επεκτείνουμε τον προσανατολισμό αυτόν σε ένα προσανατολισμό του G ως εξής:

    v_i\rightarrow u,\;\;\;i=1,2,\ldots,k

    u\rightarrow w

    w\rightarrow v_i,\;\;\;i=1,2,\ldots,k

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

    \textit{n=3}:

    v_1\rightarrow v_2,\;v_2\rightarrow v_3,\; v_3\rightarrow v_1

    \textit{n=6}:

    v_1\rightarrow v_2,\;v_1\rightarrow v_4,\;v_1\rightarrow v_6

    v_2\rightarrow v_3,\;v_2\rightarrow v_4

    v_3\rightarrow v_1,\;v_3\rightarrow v_5

    v_4\rightarrow v_3,\;v_4\rightarrow v_5,\;v_4\rightarrow v_6

    v_5\rightarrow v_1,\;v_5\rightarrow v_2,\;v_5\rightarrow v_ 6

    v_6\rightarrow v_3,\;v_6\rightarrow v_2

    Μου αρέσει!

    Σχόλιο από Pambos — Μαρτίου 8, 2012 @ 11:05 μμ

  5. Σωστές και οι δύο λύσεις. Πολύ ωραία!

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Μαρτίου 9, 2012 @ 12:01 πμ

  6. Νομίζω υπάρχει κατασκευαστική λύση στην περιπτωση που ο n είναι περιττός.
    Τοποθετήστε τις κορυφές κυκλικά και για κάθε κορυφή i προσανατολίστε τις
    ακμές e_k :=[i,i+k] , k=1,2,\ldots , \frac{n-1}{2} προς τις κορυφές i +k .
    Αυτό δίδει προσανατολισμό σε όλες τις ακμές του γραφηματος που ικανοποιεί
    το ζητούμενο.

    Στην περιπτωση που ο n είναι άρτιος δε το βλέπω..

    Μου αρέσει!

    Σχόλιο από henk&christos — Μαρτίου 9, 2012 @ 12:25 πμ

  7. Να συνεχίσω την ιδέα του henk&christos για όταν το n είναι άρτιος. Όπως στο προηγούμενο τοποθετούμε τις κορυφές κυκλικά. Διακρίνουμε δύο περιπτώσεις:

    1)\frac{n}{2} περιττός:

    Για i=1,3,5,\ldots, n-1 προσανατολίζουμε τις ακμές [i,i+k],\;\;k=1,2,\ldots,\frac{n}{2} προς τις κορυφές i+k
    και για i=2,4,6,\ldots, n προσανατολίζουμε τις ακμές [i,i+k],\;\;k=1,2,\ldots,\frac{n}{2}-1 προς τις κορυφές i+k.

    2)\frac{n}{2} άρτιος:

    Για i=1,3,\ldots, \frac{n}{2}-1,\frac{n}{2}+2,\frac{n}{2}+4,\ldots,n προσανατολίζουμε τις ακμές [i,i+k],\;\;k=1,2,\ldots,\frac{n}{2} προς τις κορυφές i+k
    και για i=2,4,\ldots, \frac{n}{2},\frac{n}{2}+1,\frac{n}{2}+3,\ldots,n-1 προσανατολίζουμε τις ακμές [i,i+k],\;\;k=1,2,\ldots,\frac{n}{2}-1 προς τις κορυφές i+k.

    Μου αρέσει!

    Σχόλιο από Pambos — Μαρτίου 9, 2012 @ 8:56 πμ

  8. Για παράδειγμα (n=6,8 )

    \textit{n=6}:

    v_1\rightarrow v_2,\;v_1\rightarrow v_3,\;v_1\rightarrow v_4
    v_2\rightarrow v_3,\;v_2\rightarrow v_4
    v_3\rightarrow v_4,\;v_3\rightarrow v_5,\;v_3\rightarrow v_6
    v_4\rightarrow v_5,\;v_4\rightarrow v_6
    v_5\rightarrow v_6,\;v_5\rightarrow v_1,\;v_5\rightarrow v_ 2
    v_6\rightarrow v_1,\;v_6\rightarrow v_2

    \textit{n=8}:

    v_1\rightarrow v_2,\;v_1\rightarrow v_3,\;v_1\rightarrow v_4,\;v_1\rightarrow v_5
    v_2\rightarrow v_3,\;v_2\rightarrow v_4,\;v_2\rightarrow v_5
    v_3\rightarrow v_4,\;v_3\rightarrow v_5,\;v_3\rightarrow v_6,\;v_3\rightarrow v_7
    v_4\rightarrow v_5,\;v_4\rightarrow v_6,\;v_4\rightarrow v_7
    v_5\rightarrow v_6,\;v_5\rightarrow v_1,\;v_5\rightarrow v_ 8
    v_6\rightarrow v_7,\;v_6\rightarrow v_8,\;v_6\rightarrow v_1,\;v_6\rightarrow v_2
    v_7\rightarrow v_8,\;v_7\rightarrow v_1,\;v_7\rightarrow v_2
    v_8\rightarrow v_1,\;v_8\rightarrow v_2,\;v_8\rightarrow v_3,\;v_8\rightarrow v_4

    Μου αρέσει!

    Σχόλιο από Pambos — Μαρτίου 9, 2012 @ 9:13 πμ

  9. Τώρα που βλέπω το παράδειγμα η λύση που έγραψα είναι λάθος( υπάρχουν και τυπογραφικά λάθη στο σχόλιο (8) αλλά η λύση στο σχόλιο (7) είναι λάθος).

    Μου αρέσει!

    Σχόλιο από Pambos — Μαρτίου 9, 2012 @ 9:41 πμ

  10. Η επαγωγική λύση του Pambos στο σχόλιο 4 είναι κατασκευαστική. Μονοδρομήστε κατάλληλα ένα πλήρη υπογράφο 6 σημείων και συνεχίστε προσθέτοντας ζευγάρια σημείων.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Μαρτίου 9, 2012 @ 8:25 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: