Eλάχιστα συνδετικά δέντρα, δένδρα ελάχιστων μονοπατιών και σε αλγοριθμικά θέματα δέντρων

Παρακάτω δίνεται ένας γράφος που απεικονίζει ένα συγκρότημα κατοικιών όπου η κύρια είσοδος στο συγκρότημα είναι ακριβώς μπροστά από την κατοικία Α και από το σημείο αυτό περνάνε όλες οι δημόσιες γραμμές διανομής των υπογείων δικτύων (νερό, φυσικό αέριο, καλωδιακή τηλεόραση, κλπ). Στον γράφο φαίνονται οι κατοικίες και οι  δρόμοι που υπάρχουν μεταξύ τους που σημειώνονται με ακμές. Τα βάρη είναι αποστάσεις. Η εταιρία θέλει να σχεδιάσει το εσωτερικό δίκτυο ώστε να περάσουν όλα τα δίκτυα κοινής ωφελείας από όλες τις κατοικίες  αλλά χρησιμοποιώντας συνολικά τις λιγότερες σωληνώσεις και καλωδιώσεις. Πως μπορεί να κατασκευάσει αυτό το δίκτυο; Σε περίπτωση ανάγκης π.χ πυρκαγιάς θα πρέπει επίσης να υπάρχει πρόβλεψη για γρήγορη εκκένωση του συγκροτήματος που μπορεί να γίνει μόνο από το σημείο Α. Είναι το προηγούμενο δίκτυο που σχεδίασε η εταιρία λύση και για την γρήγορη εκκένωση; Αν όχι, σχεδιάσατε ένα τέτοιο. Αιτιολογήσατε τον σχεδιασμό σας.

----------------------

ΑΠΑΝΤΗΣΗ

-------------------------------------------------------------------------------------------------------

Αρχικά έχουμε να σχεδιάσουμε ένα δίκτυο ώστε να περάσουν όλες οι υποδομές κοινής ωφέλειας από όλες τις κατοικείς άλλα πρέπει να χρησιμοποιήσουμε τις λιγότερες σωληνώσεις και καλωδιώσεις. Δηλαδή πρέπει να βρούμε το υπογράφηκα οπού θα έχει όλες τις κορυφές συνδεμένες Δηλαδή θέλουμε το ελάχιστο συνδετικό δέντρο και μπορούμε να τον υπολογίσουμε από τον αλγόριθμο του prim.

Ξεκινάμε από την κορυφή Α

επιλεγούμε την ακμή με το μικρότερο βάρος που η ακμής με βάρος 5  που οδηγεί στην κορυφή Μ. Έπειτα από την Μ επιλεγούμε την βάρος της μικτότερης ακμής που είναι το 2 όπου μας οδηγεί στην Ν έπειτα επιλεγούμε την ακμή με βάρος 1 και καταλήγουμε στην κορυφή Η, Συνεχίζουμε από το πορτοκαλή γράφημα επιλεγούμε την επομένη ακμή με το μικρότερο βάρος ώστε να κάνουμε πορτοκαλί την επομένη κορυφή και το πετυχαινουμε επιλεγέντας την ακμή με βάρος 3 και από την Μ καταλήγουμε στην κορυφή P, Συνεχίζουμε επιλεγέντας την ακμή με βάρος 2 που ξεκινά από την P Και καταλήγει στην E έπειτα στην D από την ακμή με βάρος 2 μετά στην F  από την ακμή με βάρος 2 . Συνεχίζουμε επιλεγέντας την ακμή με βάρος 3 που από την κορυφή Μ καταλήγει στην Β έπειτα από την Β στην C. Έπειτα  από την κορυφή P καταλέγουμε στην κορυφή G . Τέλος από την κορυφή Ν επιλεγούμε την ακμή με βάρος 4 για να  καταλήξουμε στην Κ. Τελικά καταλέγουμε στο υπογράφημα που είναι σχεδιασμένο πορτοκαλί όπως φαίνεται στο σχήμα, Εάν αθροίσουμε όλες τις ακμές δηλαδή 5+2+4+1+3+3+2+2+2+3+2=29. Δηλαδή το ελάχιστο συνδετικό δέντρο έχει μήκος 29.

Το παραπάνω υπογράφημα δεν μας βοηθά για γρήγορη εκκένωση από το σημείο Α . Το παραπάνω υπογράφαμε είναι το ελάχιστο συνδετικό δέντρο για να βρούμε το πιο σύντομο δρόμο κάθε κορυφής για την κορυφή Α πρέπει να χρησιμοποιήσουμε τον αλγόριθμο

Dijkstra , ώστε να έχουμε το συντομότερο μονοπάτι από κάθε κορυφή για την κορυφή Α, Το υπογράφαμε που θα σχηματιστεί θα είναι το σχέδιο διαφυγής από την πολη  από την πύλη Α.

Ξεκινάμε από την κορυφή Α βάζοντας σε όλες τις άλλες τις κορυφές ετικέτα + άπειρο.  Με πράσινο είναι η προσωρινές ετικέτες και με κόκκινο οι μόνιμες . Από την Α ξεκινάμε  0 και βλέπουμε τις γείτονες της Α που είναι Β και ενημερώνουμε με 7 την Μ ενημερώνουμε με 5 και την Κ με 6. Κάνουμε μόνιμη την μικρότερη ετικέτα δηλαδή την Μ .

 

Εφαρμόζω το ίδιο και για την κορυφή M βρίσκω τους γείτονες και ενημερώνω τις προσωρινές ετικέτες για την Β 8 και D με 11 και την P με 8 από τις προσωρινές ετικέτες επιλεγώ την μικρότερη που είναι στην κορυφή Κ και . οριστικοποιώ Κ ενημερώνω τους γείτονες της. Την Ν με 10 που δεν αποθηκεύεται γιατί υπάρχει προσωρινή με 7, επειτα και την Η με 11 και οριστικοποιώ την μικρότερη ετικέτα που είναι η 7 της Β. Αμέσως ενημερώνω τους γείτονες  (τους μη οριστικοποιημένους) την Β με προσωρινές ετικέτες  δηλαδή την C και ενημερώνω την προσωρινή της ετικέτα με 9. Έπειτα οριστικοποιώ την μικρότερη ετικέτα που είναι στην κορυφή Ν και έχει τιμή 7, Ενημερώνω τους γείτονες την Ν P με 11 που δεν ενημερώνει την προσωρινή ετικέτα επειδή υπάρχει το 8 και την Η με 8 σβήνοντας την παλιά. Οριστικοποιούμε την ετικέτα 8 την Η και ελέγχουμε τους γείτονες τις για ενημέρωση των ετικετών. Την G με 13 . Έπειτα οριστικοποιώ την P με 8.Ελεγχω τις γείτονες της P, τη την G σβήνοντας την παλιά ετικέτα 13 και ενημερώνω την νέα με 11 και την κορυφή Ε με 10 . Έπειτα οριστικοποιώ την κορυφή C με 9 και ελέγχω τους γείτονες της , την D με 17 που  υπάρχει προσωρινή ετικέτα με 11 και δεν  θα αντικατασταθεί. Έπειτα οριστικοποιώ την Ε με 10 και ενημερώνω τους γείτονες της  F με 12 και D με 12 που δεν θα καταχωρηθεί γιατί η D έχει ετικέτα αποθηκευμένη D. Έπειτα οριστικοποιώ την G με 11 . Ελέγχω τους γείτονες  της G  και  F με 18 όπου δεν θα καταχωρηθεί διότι F έχει 12. Έπειτα οριστικοποιώ την D με 11  ελέγχω τους γείτονες τις δεν έχει γείτονες με προσωρινές ετικέτες. Τέλος οριστικοί την F με 12.

Τελειώνοντας τον αλγόριθμο καταλήγουμε στο μωβ μονοπάτι που είναι το δίκτυο εκκένωσης .Το μοβ μονοπάτι μας δίνει το συντομότερο μονοπάτι κάθε κορυφής με την κορυφή Α που είναι η κορυφή διαφυγής από την πολη. Το μονοπάτι έχει μήκος 39.