«Ο Αρχιμήδης θα μνημονευθεί όταν ο Αισχύλος θα έχει λησμονηθεί, διότι οι γλώσσες πεθαίνουν, μα οι μαθηματικές ιδέες όχι.» G.Hardy


Δευτέρα, 9 Ιουλίου 2018

Η γειτονιά του Όιλερ


4 σχόλια:

  1. Το μέγιστο δυνατό μήκος διαδρομής από το Α έως το Β είναι 24, για τον εξής λόγο:
    Συνολικό μήκος ακμών σχήματος = 32
    Από τις 2 ή 3 ακμές που συντρέχουν σε οποιονδήποτε κόμβο, μπορούμε να διανύσουμε μόνο τις 1 ή 2 αντιστοίχως (αλλιώς θα υπήρχε υποχρεωτικά ακμή που θα διανυόταν δύο φορές).
    Για τη μεγιστοποίηση της διαδρομής από το Α μέχρι το Β, αρκεί λοιπόν σε κάθε κόμβο να διανυθούν οι μεγαλύτερες σε μήκος ν-1 ακμές από τις ν συνολικά ακμές που συντρέχουν σε αυτό τον κόμβο. Δεδομένου επίσης ότι οι ακμές διατίθενται αποκλειστικά σε μήκη 2 ή 1 κάθε μια, αρκεί όλες οι ακμές που δεν διανύονται να είναι μήκους 1. Ο ελάχιστος απαιτούμενος αριθμός μη διανυόμενων ακμών είναι 8, άρα το ελάχιστο μη διανυόμενο συνολικό μήκος ακμών 8 και επομένως το μέγιστο διανυόμενο μήκος 32-8=24.

    ΑπάντησηΔιαγραφή
  2. Διευκρίνιση: ως κόμβους θεωρώ τα σημεία επιλογής κατεύθυνσης, εφόσον υπάρχει τέτοια επιλογή.

    ΑπάντησηΔιαγραφή
  3. Συγκεκριμένα:
    Οι αριθμοί παρακάτω δείχνουν διανυόμενα μήκη ακμών και τα γράμματα κατεύθυνση (κάτω, πάνω, δεξιά, αριστερά):

    Α-2κ-2κ-1δ-2δ-1π-1π-1π-1α-2κ-1α-1π-1π-1π-2δ-1δ-2κ-2κ-Β

    Μήκος διαδρομής 24

    ΑπάντησηΔιαγραφή

Related Posts Plugin for WordPress, Blogger...