Συζητήσεις για το μάθημα

ΔΙΑΛΕΞΗ 18

ΔΙΑΛΕΞΗ 18

by VASILEIOS-TSAMPIKOS KARAGIANNIS -
Number of replies: 2

Καλησπέρα, στην διάλεξη 18 στην σελίδα 17 που εφαρμόζουμε τον αλγοριθμο Kruskal με τις συνδείμενες πόλεις π..χ στην περίπτωση ΡΩΜΗΣ-ΜΙΛΑΝΟ  Θα μπορούσατε να μας γράψετε( με τον συμβολισμό του δοθέντος σχήματος) τα δύο διαφορετικά δέντρα που ενώνει η ακμή ΡΩΜΗ-ΜΙΛΑΝΟ που την προσθέτουμε στο νέο δάσος;

ΕΥΧΑΡΙΣΤΩ

In reply to VASILEIOS-TSAMPIKOS KARAGIANNIS

Re: ΔΙΑΛΕΞΗ 18

by GEORGIOS KAPETANAKIS -
Γεια σου Βασίλη,
Στην αρχή ξεκινάμε με την κάθε κορυφή να είναι από μόνη της (κατά τετριμμένο τρόπο) ένα δέντρο. Έτσι όταν προσθέτουμε την ακμή Ρώμη-Μιλάνο ενώνουμε τα δέντρα ({Ρώμη},\(\emptyset\)) και ({Μιλάνο},\(\emptyset\)) και δημιουργούμε το δέντρο ({Ρώμη,Μιλάνο},{{Ρώμη,Μιλάνο}}), δηλαδή το δέντρο με δύο κορυφές (Ρώμη και Μιλάνο) και μια ακμή ({Ρώμη,Μιλάνο}).