Δένδρο: Μια ακμή δεν σημαίνει και μια διαδρομή;

[petrosp13]

Κανόνας 2 των δένδρων: Σε κάθε κόμβο καταλήγει μια ακμή
Κανόνας 3 των δένδρων: Για κάθε κόμβο υπάρχει μια διαδρομή που να καταλήγει σε αυτόν

Ο κανόνας 2 δεν συνεπάγεται τον κανόνα 3 και άρα ο κανόνας 3 είναι περιττός;
Καταλαβαίνω κάτι λάθος;

[pgrontas]

Πολύ σωστά.
Για μένα ο κανόνας 3, θα έπρεπε να υπάρχει στο βιβλίο, όχι ως κανόνας αλλά ως παρατήρηση - σχόλιο. Στον ορισμό είναι τελείως περιττός.

[ApoAntonis]

Όχι ακριβώς,
"Για κάθε κόμβο c, εκτός από τη ρίζα, υπάρχει μόνο μια ακμή που καταλήγει στον κόμβο αυτόν
ξεκινώντας από κάποιον άλλον κόμβο p. Ο κόμβος p ονομάζεται γονέας του c και ο κόμβος c
παιδί του p."

Το δεύτερο δεν λέει ότι στον κόμβο c καταλήγει μοναδική ακμή.
Λέει ότι μεταξύ των c-p υπάρχει μοναδική ακμή.

(* δεν λέω ότι έχει γραφτεί καλά)

[petrosp13]

Άρα ο ορισμός εννοεί ότι δεν υπάρχουν δυο ακμές μεταξύ δυο κόμβων;
Αν αυτό είναι το νόημα, θεωρώ πολύ ατυχή την διατύπωση και ότι οι κανόνες 2-3 θα μπορούσαν να συγχωνευτούν σε μια πιο σαφή πρόταση

[pgrontas]

Δεν ξέρω αν καταλαβαίνω καλά: Αν δεν υπάρχουν δύο ακμές μεταξύ δύο κόμβων (2) τότε πάλι περιττό δεν είναι το (3);

[petrosp13]

Μάλλον εννοεί αυτό

Α-->Β-->Γ
Α-->Δ-->Γ

Ανάμεσα στους κόμβους υπάρχει μια σύνδεση αλλά δεν υπάρχει μια διαδρομή για το Γ
Δηλαδή δεν υπάρχουν δυο συνδέσεις ανάμεσα στο Α και το Β ή το Α και το Δ
Ανούσιο εντελώς

[pgrontas]

Αυτό παραβιάζει και το (2) γιατί το γ δεν έχει μοναδικό γονέα. 

Μάλλον εννοεί αυτό

Α-->Β-->Γ
Α-->Δ-->Γ

Ανάμεσα στους κόμβους υπάρχει μια σύνδεση αλλά δεν υπάρχει μια διαδρομή για το Γ
Δηλαδή δεν υπάρχουν δυο συνδέσεις ανάμεσα στο Α και το Β ή το Α και το Δ
Ανούσιο εντελώς

Τέλος πάντων το συγκεκριμένο ερώτημα με προβλημάτιζε από όταν το πρωτοείδα. Προσωπικά δεν κατάφερα να βρω ένα παράδειγμα που να μην παραβιάζεται και το (2) και το (3).

[ApoAntonis]

Δεν ξέρω αν καταλαβαίνω καλά: Αν δεν υπάρχουν δύο ακμές μεταξύ δύο κόμβων (2) τότε πάλι περιττό δεν είναι το (3);

Όχι. Θεωρείς δεδομένο ότι κάθε κόμβος έχει μια εισερχόμενη ακμή (έναν γονέα), κάτι που δεν διατυπώνεται στον ορισμό.

Μάλλον εννοεί αυτό

Α-->Β-->Γ
Α-->Δ-->Γ

ή
Α-->Β-->Γ
Α --> Γ

[pgrontas]

Όχι. Θεωρείς δεδομένο ότι κάθε κόμβος έχει μια εισερχόμενη ακμή (έναν γονέα), κάτι που δεν διατυπώνεται στον ορισμό.


ή
Α-->Β-->Γ
Α --> Γ

Διαφωνώ, ο ορισμός (2) λέει επι λέξει:

Για κάθε κόμβο c, εκτός από τη ρίζα, υπάρχει μόνο μια ακμή που καταλήγει στον κόμβο αυτόν ξεκινώντας από κάποιον άλλον κόμβο p. Ο κόμβος p ονομάζεται γονέας του c και ο κόμβος c παιδί του p.

Αυτό σημαίνει μόνο ένας γονέας.

[petrosp13]

Όπως και να έχει, οι κανόνες 2 και 3 θα μπορούσαν σίγουρα να συγχωνευτούν σε έναν πιο σύντομο και περιεκτικό κανόνα

[ApoAntonis]

Διαφωνώ, ο ορισμός (2) λέει επι λέξει:

Αυτό σημαίνει μόνο ένας γονέας.

Δεν λέει μόνο ένας γονέας.
Είπα προηγουμένως αυτό ακριβώς πέρα από τον τρίτο "κανόνα", δεν υπάρχει αναφορά σε μοναδικό γονέα.
Το δύο δεν αποκλείει (έτσι όπως είναι γραμμένο εννοώ) ότι ο c έχει πολλαπλούς γονείς.

[pgrontas]

Κατάλαβα τη διαφορά μας. Εγώ το ερμηνεύω ως μόνο μια ακμή σκέτο, εσύ το ερμηνεύεις ως μόνο μια ακμή ανά γονέα. Εξακολουθώ να μη συμφωνώ, αλλά ας το ληξω εδώ, γιατί δεν έχει αξία να διυλιζουμε τον κωνωπα και να κάνουμε συζήτηση για κάτι τόσο άθλια γραμμένο.

Δεν λέει μόνο ένας γονέας.
Είπα προηγουμένως αυτό ακριβώς πέρα από τον τρίτο "κανόνα", δεν υπάρχει αναφορά σε μοναδικό γονέα.
Το δύο δεν αποκλείει (έτσι όπως είναι γραμμένο εννοώ) ότι ο c έχει πολλαπλούς γονείς.

[petrosp13]

για κάτι τόσο άθλια γραμμένο.

Και η πλάκα είναι ότι για 20 χρόνια φωνάζουμε για το κακογραμμένο βασικό βιβλίο και τελικά και το καινούριο έχει αρκετά προβληματικά σημεία...

[gpapargi]

Και η πλάκα είναι ότι για 20 χρόνια φωνάζουμε για το κακογραμμένο βασικό βιβλίο και τελικά και το καινούριο έχει αρκετά προβληματικά σημεία...

Από τον τρόπο που είναι γραμμένη η υλοποίηση σε στοίβα και ουρά, φάνηκε ότι προκειται για δουλειά στο γόνατο.

[Λαμπράκης Μανώλης]

Από τον τρόπο που είναι γραμμένη η υλοποίηση σε στοίβα και ουρά, φάνηκε ότι προκειται για δουλειά στο γόνατο.

Και πέρα απο το επιστημονικό κομμάτι του θέματος,  υπάρχει και το πρακτικό, δηλαδή τι να πούμε στους μαθητές οι οποίοι βλέπουν πχ στην ουρά "πίσω =Ν" να συνεπάγεται " γεμάτη ουρά " δίχως να είναι απαραίτητα, τα στοιχεία σε μια απώθηση να αναφέρεται πως δεν διαγράφονται, αλλά τα διαγραφεί στις ασκήσεις, αλλά τελικά να τα ζητάει με τα στοιχεία στις πανελλήνιες και πολλά άλλα...δυστυχώς η ερώτηση " και αν μπει πανελλήνιες  πως να το χειριστώ " σε εμένα υπάρχει συχνά, και αντε να απαντήσεις.. 

[gpapargi]

Με αφορμή τη συζήτηση έκανα μια προσπάθεια να αποδείξω ότι οι υποθέσεις (2) και (3) είναι ισοδύναμες. Τις αναφέρω αρχικά από το βιβλίο:

Υπόθεση (2):

«Για κάθε κόμβο c, εκτός από τη ρίζα, υπάρχει μόνο μια ακμή που καταλήγει στον κόμβο αυτόν ξεκινώντας από κάποιον άλλον κόμβο p. Ο κόμβος p ονομάζεται γονέας του c και ο κόμβος c παιδί του p.»
Θα τη λέω και υπόθεση «μοναδικού γονέα».

Υπόθεση (3)

Για κάθε κόμβο υπάρχει μία μοναδική διαδρομή, δηλαδή, μια ακολουθία διαδοχικών ακμών, που ξεκινάει από τη ρίζα και τερματίζει σε αυτόν τον κόμβο

Θα τη λέω και «υπόθεση μοναδικής διαδρομής από τη ρίζα».

Η σκέψη μου είναι η εξής:

(2)==>(3)

Κάθε κόμβος c έχει μοναδικό γονέα p. Ανεβαίνουμε ένα επίπεδο παραπάνω δηλαδή εφαρμόζουμε αυτή την υπόθεση θέτοντας για παιδί c τον γονέα p. Αυτός έχει επίσης ένα δικό του μοναδικό γονέα, έστω p2. Αν εφαρμόσουμε διαδοχικά αυτή τη διαδικασία κάθε φορά θέτοντας ως  παιδί το γονέα του προηγούμενου επιπέδου φτάνουμε αναπόφευκτα στη ρίζα. Η διαδρομή είναι μοναδική γιατί κάθε φορά ο γονιός ήταν μοναδικός λόγω της (2). Αν διασχίσουμε αυτή τη διαδρομή ανάποδα δηλαδή από τη ρίζα προς το αρχικό c, προκύπτει η (3).
 
Αντίστροφα (3)==>(2)

Έστω ότι υπάρχει κόμβος c με δύο γονείς τους p1 και p2. Από την (3) υπάρχει μοναδική διαδρομή από τον p1 προς τη ρίζα και επίσης μοναδική διαδρομή από τον p2 προς τη ρίζα. Άρα έχουμε δύο διαδρομές από το c προς τη ρίζα (μία μέσω του p1 και μια μέσω του p2. Διαγράφοντάς τις ανάποδα έχουμε δύο διαδρομές από τη ρίζα προς το c. Άτοπο από (3) που απαιτεί να έχουμε μοναδική διαδρομή και για τον c. Άρα δεν υπάρχει κόμβος με δύο γονείς. Άρα ισχύει η (2).
 
Ελπίζω να μη μου ξέφυγε κάτι.

[akalest0s]

Και η πλάκα είναι ότι για 20 χρόνια φωνάζουμε για το κακογραμμένο βασικό βιβλίο και τελικά και το καινούριο έχει αρκετά προβληματικά σημεία...

Το "αρκετά" είναι ο πιο επιεικής χαρακτηρισμός που μπορώ να φανταστώ!

@gpapargi
Το πρόβλημα που (με τραβηγμένο -αλλά όχι λανθασμένο- τρόπο) θίγει ο ApoAntonis, είναι ότι η διατύπωση του (2) αφήνει περιθώριο για πολλαπλούς γονείς p οι οποίοι έχουν μοναδική ακμή προς τον κόμβο c. Προφανώς δεν θέλαν να πουν αυτό, αλλά.. τους ξέφυγε. Ευτυχώς δεν εξετάζεται σε πανελλήνιες το μάθημα. Φαντάζεσαι;

[ApoAntonis]

Χάρη της συζήτησης και σίγουρα έξω από τα πλαίσια του μαθήματος.
Νομίζω ότι πρωταρχικό πρόβλημα δημιουργείται επειδή παρουσιάζονται πρώτα τα δέντρα και ύστερα οι γράφοι.
Το ανάποδο θα ήταν φυσιολογικό. Οι -ας πούμε έτσι- ιδιότητες των γράφων δεν εξηγούνται και  δεν αναλύονται και όπως καταλαβαίνω δεν μας ενδιαφέρουν.
Καλύτερα ίσως σε τέτοια περίπτωση να είχαν παραλείψει εντελώς την αναφορά.

Γυρίζουμε στα δέντρα. Με διαφορετικό ορισμό, οι κανόνες -ο τρίτος οπωσδήποτε ίσως και ο δεύτερος ανάλογα τον ορισμό- που αναφέρονται είναι ιδίοτητες των δένδρων, άμεσες και μάλλον προφανείς (σημείωση συνεχίζω εκτός διδακτικής και έξω από το μάθημα).

Με αφορμή τη συζήτηση έκανα μια προσπάθεια να αποδείξω ότι οι υποθέσεις (2) και (3) είναι ισοδύναμες. Τις αναφέρω αρχικά από το βιβλίο:

Υπόθεση (2):

«Για κάθε κόμβο c, εκτός από τη ρίζα, υπάρχει μόνο μια ακμή που καταλήγει στον κόμβο αυτόν ξεκινώντας από κάποιον άλλον κόμβο p. Ο κόμβος p ονομάζεται γονέας του c και ο κόμβος c παιδί του p.»
Θα τη λέω και υπόθεση «μοναδικού γονέα».

η υπόθεση 2 δεν απαγορεύει το μονοπάτι: Α->Β->Α (είναι κατευθυνόμενο δένδρο και δεν αναφέρεται στο ορισμό, υπάρχει έλλειψη)
Δεν ορίζεται στον ορισμό (πλεονασμός ) βαθμός εισερχόμενων ακμών.
Φαίνεται φυσιολογικό μεν, αλλά δεν προσδιορίζεται αλλού ότι δύο κόμβοι (μπορούν να) ενώνονται με μοναδική ακμή. Αυτό κάνει η υπόθεση 2.

Η σκέψη μου είναι η εξής:

(2)==>(3)

αν η 2 συνεπάγεται την 3, πρέπει η άρνηση της 3 να συνεπάγεται την άρνηση της 2.

Δηλαδή αν υπάρχει παραπάνω από ένα μονοπάτι μεταξύ δύο κόμβων, τότε σε αυτήν την διαδρομή δύο κόμβοι -διαδοχικοί για να γίνει κατανοητό- κάπου μέσα στο μονοπάτι ενώνονται με παραπάνω από μια ακμή,
το οποίο δεν ισχύει στο παράδειγμα που είδαμε:

Α-->Β-->Γ
Α-->Δ-->Γ

ή στο

Α-->Β-->Γ
Α --> Γ

[gpapargi]

Αυτά που γράφω θεωρούν ως προϋπόθεση ότι η (2) ερμηνεύεται σαν "μοναδικός γονέας". Αν αυτό δεν είναι δεκτό τότε προφανώς δεν ισχύει το επιχείρημα. Οι κυκλικές συνδέσεις παραβιάζουν την υπόθεση του "μοναδικού γονέα".

[gpapargi]

@gpapargi
Το πρόβλημα που (με τραβηγμένο -αλλά όχι λανθασμένο- τρόπο) θίγει ο ApoAntonis, είναι ότι η διατύπωση του (2) αφήνει περιθώριο για πολλαπλούς γονείς p οι οποίοι έχουν μοναδική ακμή προς τον κόμβο c. 

Αν καταλαβαίνω καλά η διατύπωση μπορεί να ερμηνευτεί λέγοντας ότι ο p δεν είναι μοναδικός.
Το ερώτημα είναι αν μπορώ, τραβώντας το λίγο ακόμα, να το ερμηνεύσω ως εξής: "υπάρχει p όχι μοναδικός και αυτός/αυτοί είναι οι γονείς. ΑΛΛΑ μπορεί να υπάρχει και κάποιος άλλος κόμβος α με διπλή σύνδεση με τον c που απλά δεν είναι γονιός". Αφήνεται περιθώριο για τέτοια τραβηγμένη ερμηνεία ή όχι;