ΠΛΗ20 Μάθημα 6.2 – Συνδετικά Δένδρα


Στόχοι του Μαθήματος

Στο μάθημα αυτό:

  • Ορίζουμε το συνδετικό δένδρο ενός γραφήματος και μελετάμε τους αλγορίθμους Κατά Βάθος και Κατά Πλάτος που το υπολογίζουν.
  • Ορίζουμε το ελάχιστο συνδετικό δένδρο ενός γραφήματος με βάρη και μελετάμε τον αλγόριθμο Prim που το υπολογίζουν.

Σύντομη Παρουσίαση

Με μια ματιά το μάθημα:

  • ΚΑΡΤΑ: Συνδετικά Δέδνρα
  • ΚΑΡΤΑ: Διάσχιση Κατά Βάθος
  • ΚΑΡΤΑ: Διάσχιση Κατά Πλάτος
  • ΚΑΡΤΑ: Αλγόριθμος Prim
  • ΚΑΡΤΑ: Σύγκριση Αλγορίθμων


Σχολιασμός (βίντεο)

Αναλυτική Παρουσίαση

ΠΕΡΙΕΧΟΜΕΝΑ ΜΑΘΗΜΑΤΟΣ:

1) Ορισμός Συνδετικού Δένδρου
1.1) Διάσχιση Πρώτα Κατά Πλάτος
1.2) Διάσχιση Πρώτα Κατά Βάθος
2) Ελάχιστο Συνδετικό Δένδρο
2.1) Ορισμός Ελάχιστου Συνδετικού Δένδρου
2.2) Ο αλγόριθμος του Prim
3) Σύνοψη για τους Αλγόριθμους
3.1) Συντομότερα Μονοπάτια
3.2) Συνδετικό Δένδρο
3.3) Ελάχιστο Συνδετικό Δένδρο
Ασκήσεις

Παρουσίαση τουΜαθήματος:


ΒΙΝΤΕΟ ΜΑΘΗΜΑΤΟΣ και ΣΧΟΛΙΑΣΜΟΣ

ΣΥΜΒΟΥΛΕΣ

 penguin.200  batman.200
ΚατηγορίαΧΔΣχόλιο
Θεωρία 1 από 4Διάσχιση Κατά Βάθος
Θεωρία 2 από 4Διάσχιση Κατά Πλάτος
Θεωρία 3 από 4Ελάχιστο Συνδετικό Δένδρο και ο Αλγόριθμος του Prim
Θεωρία 4 από 4Χρήσεις των αλγορίθμων Dijkstra, Prim, Κατά Βάθος, Κατά Πλάτος για την επίλυση προβλημάτων.
Κατανόηση 151Παράδειγμα Εκτέλεσης Αλγόριθμου Prim, Κατά Βάθος και Κατά Πλάτος
Κατανόηση 251Παράδειγμα Εκτέλεσης αλγορίθμου Prim και αλγορίθμου Kruskal
Κατανόηση 353Ιδιότητες Ελάχιστων Συνδετικών Δένδρων
Κατανόηση 453Παράδειγμα Εκτέλεσης των αλγορίθμων Prim και Kruskal
Ερωτήσεις 153Εκτέλεση Αλγορίθμου Prim
Ερωτήσεις 253Ιδιότητες των Συνδετικών Δένδρων
Ερωτήσεις 353Εκτέλεση των Αλγορίθμων Κατά Βάθος και Κατά Πλάτος
Ερωτήσεις 453Ιδιότητες των Δένδρων που παράγουν οι Κατά βάθος και Κατά Πλάτος σε συγκεκριμένες οικογένειες γραφημάτων
Εφαρμογή 143Διατήρηση του ΕΣΔ όταν κάθε ακμή πολλαπλασιάζεται με το ίδιο βάρος
Εφαρμογή 254Διατήρηση του ΕΣΔ όταν σε κάθε ακμή προστίθεται το ίδιο βάρος
Εφαρμογή 343Ελάχιστο Συνδετικό Δένδρο που περιλαμβάνει υποχρεωτικά ακμή.
Εφαρμογή 453Αλγόριθμος που αποφασίζει αν ένα γράφημα είναι άκυκλο και συνδεόμενο
Εφαρμογή 543"Όταν όλα τα βάρη ενός γραφήματος είναι διαφορετικά, τότε το ελάχιστο συνδετικό δένδρο είναι μοναδικό.

Περαιτέρω Εξάσκηση

(-)

Πηγές και Διαδίκτυο

Οι λυμένες ασκήσεις και οι ερωτήσεις είναι θέματα εξετάσεων-εργασιών του ΕΑΠ

Εκτυπώσιμη μορφή αρχείων PDF