Σελίδα 1 από 1
Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Δημοσιεύτηκε: Παρ Σεπ 04, 2015 3:33 pm
από Demetres
Το πιο κάτω σχήμα αποτελείται από 16 ευθύγραμμα τμήματα. Να αποδειχθεί ότι δεν υπάρχει καμπύλη η οποία να τέμνει κάθε τμήμα από ακριβώς μία φορά.
Η καμπύλη δεν πρέπει απαραίτητα να είναι κλειστή, επιτρέπεται να τέμνει τον εαυτό της, αλλά απαγορεύεται να εφάπτεται των τμημάτων ή να περνά από τις κορυφές.
![\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\clip(-2.42,-6.1) rectangle (9.18,3.36);
\draw [line width=1.2pt] (-2.,3.)-- (-2.,1.);
\draw [line width=1.2pt] (-2.,1.)-- (2.,1.);
\draw [line width=1.2pt] (2.,1.)-- (2.,3.);
\draw [line width=1.2pt] (2.,3.)-- (-2.,3.);
\draw [line width=1.2pt] (-2.,2.)-- (2.,2.);
\draw [line width=1.2pt] (0.,3.)-- (0.,2.);
\draw [line width=1.2pt] (-1.,2.)-- (-1.,1.);
\draw [line width=1.2pt] (1.,2.)-- (1.,1.);
\begin{scriptsize}
\draw [fill=black] (-2.,2.) circle (1.5pt);
\draw [fill=black] (-1.,2.) circle (1.5pt);
\draw [fill=black] (0.,2.) circle (1.5pt);
\draw [fill=black] (1.,2.) circle (1.5pt);
\draw [fill=black] (2.,2.) circle (1.5pt);
\draw [fill=black] (-2.,3.) circle (1.5pt);
\draw [fill=black] (2.,3.) circle (1.5pt);
\draw [fill=black] (0.,3.) circle (1.5pt);
\draw [fill=black] (-2.,1.) circle (1.5pt);
\draw [fill=black] (-1.,1.) circle (1.5pt);
\draw [fill=black] (1.,1.) circle (1.5pt);
\draw [fill=black] (2.,1.) circle (1.5pt);
\end{scriptsize}
\end{tikzpicture}](/forum/ext/geomar/texintegr/latexrender/pictures/e4664e41afb5ef73d0001a1a7ee74976.png "\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\clip(-2.42,-6.1) rectangle (9.18,3.36);
\draw [line width=1.2pt] (-2.,3.)-- (-2.,1.);
\draw [line width=1.2pt] (-2.,1.)-- (2.,1.);
\draw [line width=1.2pt] (2.,1.)-- (2.,3.);
\draw [line width=1.2pt] (2.,3.)-- (-2.,3.);
\draw [line width=1.2pt] (-2.,2.)-- (2.,2.);
\draw [line width=1.2pt] (0.,3.)-- (0.,2.);
\draw [line width=1.2pt] (-1.,2.)-- (-1.,1.);
\draw [line width=1.2pt] (1.,2.)-- (1.,1.);
\begin{scriptsize}
\draw [fill=black] (-2.,2.) circle (1.5pt);
\draw [fill=black] (-1.,2.) circle (1.5pt);
\draw [fill=black] (0.,2.) circle (1.5pt);
\draw [fill=black] (1.,2.) circle (1.5pt);
\draw [fill=black] (2.,2.) circle (1.5pt);
\draw [fill=black] (-2.,3.) circle (1.5pt);
\draw [fill=black] (2.,3.) circle (1.5pt);
\draw [fill=black] (0.,3.) circle (1.5pt);
\draw [fill=black] (-2.,1.) circle (1.5pt);
\draw [fill=black] (-1.,1.) circle (1.5pt);
\draw [fill=black] (1.,1.) circle (1.5pt);
\draw [fill=black] (2.,1.) circle (1.5pt);
\end{scriptsize}
\end{tikzpicture}")
Πηγή: Σοβιετική Ένωση 1961
Re: Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Δημοσιεύτηκε: Παρ Σεπ 04, 2015 3:51 pm
από Mihalis_Lambrou
Πρόκειται για πάρα πολύ ωραία άσκηση. Δεν γράφω λύση γιατί την γνωρίζω ήδη αλλά θέλω μόνο να προσθέσω ότι
η άσκηση απευθυνόταν σε μαθητές Γυμνασίου. Ο Διαγωνισμός από όπου προέρχεται, είναι καταπληκτικός.
Παρακαλώ να μην γράψουν λύση όσοι την έχουν ξαναδεί (κυκλοφορεί και στην ελληνική - μεταφρασμένη - βιβλιογραφία).
Re: Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Δημοσιεύτηκε: Παρ Σεπ 04, 2015 4:33 pm
από Demetres
Mihalis_Lambrou έγραψε:Ο Διαγωνισμός από όπου προέρχεται, είναι καταπληκτικός.
Πράγματι έτσι είναι. Μου ζητήθηκε πρόσφατα να βάλω περισσότερες ασκήσεις συνδυαστικής. Θα αντλήσω σίγουρα πολλές από αυτόν τον διαγωνισμό. (Από εκεί άλλωστε αντλεί και ο Engel αρκετές από τις ασκήσεις του.)
Ένας άλλος διαγωνισμός με πολύ καλές ασκήσεις είναι ο tournament of the towns. Έβαλα ήδη
εδώ και
εδώ τις ασκήσεις από τον πρώτο διαγωνισμό αλλά ακόμη δεν υπήρξε μεγάλη ανταπόκριση.
Re: Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Δημοσιεύτηκε: Πέμ Σεπ 10, 2015 2:54 pm
από Demetres
Demetres έγραψε:Το πιο κάτω σχήμα αποτελείται από 16 ευθύγραμμα τμήματα. Να αποδειχθεί ότι δεν υπάρχει καμπύλη η οποία να τέμνει κάθε τμήμα από ακριβώς μία φορά.
Η καμπύλη δεν πρέπει απαραίτητα να είναι κλειστή, επιτρέπεται να τέμνει τον εαυτό της, αλλά απαγορεύεται να εφάπτεται των τμημάτων ή να περνά από τις κορυφές.
Πηγή: Σοβιετική Ένωση 1961
Βοήθεια: Ας υποθέσουμε πως υπάρχει τέτοια καμπύλη η οποία ξεκινάει από το πάνω αριστερά κουτάκι. Πρέπει να καταλήξει μέσα ή έξω από αυτό το κουτάκι;
Re: Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Δημοσιεύτηκε: Δευ Οκτ 31, 2016 6:17 pm
από Demetres
Επαναφορά.
Re: Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Δημοσιεύτηκε: Τρί Νοέμ 01, 2016 12:29 am
από Mihalis_Lambrou
Demetres έγραψε:Το πιο κάτω σχήμα αποτελείται από 16 ευθύγραμμα τμήματα. Να αποδειχθεί ότι δεν υπάρχει καμπύλη η οποία να τέμνει κάθε τμήμα από ακριβώς μία φορά.
Η καμπύλη δεν πρέπει απαραίτητα να είναι κλειστή, επιτρέπεται να τέμνει τον εαυτό της, αλλά απαγορεύεται να εφάπτεται των τμημάτων ή να περνά από τις κορυφές.
Για να κλείνει η ωραία αυτή άσκηση:
Μπορούμε να θεωρήσουμε ότι τα "κουτάκια" είναι δωμάτια και ότι έχουν σημειωθεί οι πόρτες που συνδέουν τα δωμάτια μεταξύ τους ή με τον εξωτερικό χώρο. Παρατηρούμε ότι μερικά από τα δωμάτια έχουν από
πόρτες (τα γαλάζια) ενώ τα υπόλοιπα (τα πράσινα) έχουν από
.
Θέλουμε μία διαδρομή που να περνά από όλες τις πόρτες, μία φορά την καθεμία.
Τα δωμάτια που έχουν
πόρτες πρέπει να είναι στην αρχή ή στο τέλος της διαδρομής διότι σε αυτά πρέπει να "μπεις και να βγεις" δύο φορές και άλλη μία για να μπεις (χωρίς να ξαναβγεις) ή το ανάποδο, δηλαδή να βγεις (χωρίς να ξαναμπείς).
Όμως τα δωμάτια με τις
πόρτες είναι τρία τον αριθμό, ενώ τα άκρα της διαδρομής είναι μόνον δύο. Οπότε δεν υπάρχει διαδρομή που να περνά όλες τις πόρτες από μία φορά.
.
Re: Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Δημοσιεύτηκε: Τρί Νοέμ 01, 2016 6:46 am
από taratoris
Εάν θεωρήσουμε οτι το κάθε δωμάτιο είναι μία κορυφή γράφου (συμπεριλαμβάνουμε ως δωμάτιο το εξωτερικό χωρίο) και κάθε κοινή πλευρά ανάμεσα σε δωμάτια είναι μία ακμή, τότε δημιουργείται γράφος με 6 κορυφές. Η κορυφή που συμβολίζει το εξωτερικό χωρίο είναι σε επαφή με 9 ακμές, 3 κορυφές είναι σε επαφή με 5 ακμές και 2 κορυφές ειναι σε επαφή με 4 ακμές.
Το πρόβλημα είναι εάν μπορούμε ξεκινώντας απο οποιαδήποτε κορυφή να διανύσουμε όλες τις ακμές ακριβώς μία φορά. Κάθε κορυφή με περιττό πλήθος ακμών πρέπει είτε να είναι η αρχική είτε η τελική κορυφή. Εφόσον υπάρχουν 4 τέτοιες κορυφές συμπεραίνουμε οτι δεν υπάρχει λύση.
Ουσιαστικά αυτή είναι η λύση του κύριου Λάμπρου, δεν πρόσθεσα κάτι καινούριο. Απλώς παρέθεσα μία διαφορετική οπτική του προβλήματος ως γράφου.
Απο ποιόν διαγωνισμό είναι το πρόβλημα?
Re: Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Δημοσιεύτηκε: Τρί Νοέμ 01, 2016 9:04 am
από gbaloglou
Ειδική περίπτωση του Θεωρήματος Euler, πρώτου ιστορικά της Θεωρίας Γράφων, που εμπνεύστηκε στην προσπάθεια του να επιλύσει το πρόβλημα των επτά γεφυρών της Καινιξβέργης (
Seven Bridges of Königsberg): οι ντόπιοι προσπαθούσαν να αρχίσουν και να τελειώσουν τον περίπατο τους στην πόλη διασχίζοντας κάθε μία από τις επτά γέφυρες της ακριβώς μία φορά
Re: Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Δημοσιεύτηκε: Τρί Νοέμ 01, 2016 4:27 pm
από Demetres
taratoris έγραψε:
Απο ποιόν διαγωνισμό είναι το πρόβλημα?
Είναι από την πρώτη πανρωσική ολυμπιάδα του 1961. Μπορείτε να δείτε τα προβλήματα από το 1961 ως το 1986 στα αγγλικά
εδώ.
gbaloglou έγραψε:Ειδική περίπτωση του Θεωρήματος Euler, πρώτου ιστορικά της Θεωρίας Γράφων, που εμπνεύστηκε στην προσπάθεια του να επιλύσει το πρόβλημα των επτά γεφυρών της Καινιξβέργης (
Seven Bridges of Königsberg): οι ντόπιοι προσπαθούσαν να αρχίσουν και να τελειώσουν τον περίπατο τους στην πόλη διασχίζοντας κάθε μία από τις επτά γέφυρες της ακριβώς μία φορά
Ας πούμε και τι λέει: Ένα γράφημα
έχει μονοπάτι Euler αν και μόνο το
είναι συνεκτικό και έχει το πολύ δύο κορυφές περιττού βαθμού.
Ορολογία:
Μονοπάτι Euler: Μετακίνηση μεταξύ των κορυφών μέσω ακμών η οποία χρησιμοποιεί όλες τις ακμές ακριβώς από μία φορά.
Συνεκτικό γράφημα: Μπορούμε να μετακινηθούμε από κάθε κορυφή σε οποιαδήποτε άλλη χρησιμοποιώντας μόνο ακμές. (Ίσως όχι απευθείας.)
Βαθμός κορυφής: Με πόσες άλλες κορυφές συνδέεται απευθείας αυτή η κορυφή μέσω ακμών.
Ουσιαστικά το «μόνο αν» έχει αποδειχθεί.
Re: Καμπύλη που να τέμνει κάθε τμήμα από μία φορά
Δημοσιεύτηκε: Τρί Νοέμ 01, 2016 7:48 pm
από gbaloglou
Demetres έγραψε:taratoris έγραψε:
Απο ποιόν διαγωνισμό είναι το πρόβλημα?
Είναι από την πρώτη πανρωσική ολυμπιάδα του 1961. Μπορείτε να δείτε τα προβλήματα από το 1961 ως το 1986 στα αγγλικά
εδώ.
gbaloglou έγραψε:Ειδική περίπτωση του Θεωρήματος Euler, πρώτου ιστορικά της Θεωρίας Γράφων, που εμπνεύστηκε στην προσπάθεια του να επιλύσει το πρόβλημα των επτά γεφυρών της Καινιξβέργης (
Seven Bridges of Königsberg): οι ντόπιοι προσπαθούσαν να αρχίσουν και να τελειώσουν τον περίπατο τους στην πόλη διασχίζοντας κάθε μία από τις επτά γέφυρες της ακριβώς μία φορά
Ας πούμε και τι λέει: Ένα γράφημα
έχει μονοπάτι Euler αν και μόνο το
είναι συνεκτικό και έχει το πολύ δύο κορυφές περιττού βαθμού.
Ακριβέστερα, υπάρχει κύκλωμα Euler (που αρχίζει και τελειώνει στην ίδια κορυφή, Euler circuit) αν και μόνον αν όλες οι κορυφές είναι αρτίου βαθμού, και μονοπάτι Euler (που αρχίζει σε μία κορυφή και τελειώνει σε μιαν άλλη, Euler path) αν και μόνον αν υπάρχουν δύο ακριβώς κορυφές περιττού βαθμού (η αρχή και το τέλος του μονοπατιού).