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

[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 που απλά δεν είναι γονιός". Αφήνεται περιθώριο για τέτοια τραβηγμένη ερμηνεία ή όχι;