Η ελάχιστη τομή (minimum cut ή min cut) ενός γραφήματος είναι το μικρότερο σύνολο ακμών των οποίων η αφαίρεση αποσυνδέει το γράφημα σε δύο ή περισσότερα εξαρτήματα. Αντιπροσωπεύει την "αχίλλειος πτέρνα" της συνδεσιμότητας ενός δικτύου και αποτελεί κρίσιμο μέτρο για την αξιολόγηση ανθεκτικότητας, χωρητικότητας και δομικής ευωδυνότητας.
Το min cut αναδεικνύει τις ακμές των οποίων η αποτυχία προκαλεί τη μεγαλύτερη διαταραχή. Σε δίκτυα επικοινωνιών, μεταφορών ή ενέργειας, αυτές οι συνδέσεις είναι:
Το μέγεθος του min cut (αριθμός ακμών ή συνολικό βάρος σε σταθμισμένα γράφημα) δίνει αριθμητικό μέτρο ευωδυνότητας:
Ένα από τα πιο σημαντικά θεωρήματα της θεωρίας γραφημάτων: η μέγιστη ροή που μπορεί να στείλει από κόμβο s σε κόμβο t ισούται με την χωρητικότητα της ελάχιστης τομής που χωρίζει το s από το t. Εφαρμογές:
Μικρό min cut σημαίνει ότι μικρές διαταραχές απομονώουν τμήματα δικτύου. Προκαλεί:
Η κατανόηση του min cut καθοδηγεί το σχεδιασμό ανθεκτικών δικτύων:
Το min cut είναι πολύ περισσότερο από θεωρητική έννοια—είναι διαγνωστικό εργαλείο για την ανθεκτικότητα πραγματικών δικτύων. Μεγαλύτερο min cut μεταφράζεται σε υψηλότερη ευωδυνότητα, ανθεκτικότητα σε αποτυχίες και καλύτερη απόδοση υπό φόρτο. Η αναλυτική του αξιολόγηση είναι αναγκαία βήμα στον σχεδιασμό και λειτουργία οποιουδήποτε κρίσιμου υποδομικού δικτύου.
Πνευματικά δικαιώματα © Γνώση Υπολογιστών Όλα τα δικαιώματα διατηρούνται.