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