Έχουμε ένα γράφημα $G$ και θέλουμε να διαμερίσουμε το σύνολο κορυφών του $V$ σε δύο μέρη $$ V = V_1 \cup V_2 $$ έτσι ώστε να ελαχιστοποιήσουμε το πλήθος των ακμών που ενώνουν μια ακμή του $V_1$ με μια ακμή του $V_2$. Αυτό είναι το πρόβλημα εύρεσης του min-cut.
Δεν είναι εύκολο πρόβλημα μια και το πλήθος των διαμερίσεων για $n$ κορυφές είναι της τάξης του $2^n$ οπότε ο προφανής αλγόριθμος (ελέγχουμε όλες τις διαμερίσεις) είναι εκθετικός και μη πρακτικός.
Είδαμε σήμερα ένα randomized αλγόριθμο που σε χρόνο της τάξης του $n^2$ μας βρίσκει ένα min-cut με πιθανότητα τουλάχιστον $\frac{1}{2n(n-1)}$. Είδαμε ότι αν επαναλάβουμε τον αλγόριθμο αυτό περίπου $n^2 \log n$ φορές (και κρατήσουμε το μικρότερο cut που βρούμε στις επαναλήψεις) τότε μπορούμε να μειώσουμε την πιθανότητα αποτυχίας σε κάτι πολύ μικρό (π.χ. $1/n$).
Ο αλγόριθμος σε λεπτομέρειες είναι εδώ.
Μετά από την ανάλυση του αλγορίθμου ασχοληθήκαμε με την υλοποίησή του και το ημιτελές πρόγραμμα που γράψαμε φαίνεται παρακάτω.
import numpy as np
n = 5 # πλήθος κορυφών
V = {} # λεξικό που θα έχει τα ονόματα των κορυφών ως κλειδιά και για κάθε κορυφή
# θα έχει σε μια λίστα τους γείτονές της
# Αυτό θα είναι το γράφημα με το οποίο θα δουλέψουμε αρχικά
V = { '0': ['1', '3', '4'],
'1': ['0', '2', '3'],
'2': ['1', '3'],
'3': ['0', '1', '2'],
'4': ['0']
}
W = V.copy() # φτιάχνουμε ένα αντίγραφο του γραφήματος το οποίο θα αλλάζει κατά τη διάρκεια του αλγορίθμου
# Θα κάνουμε συνολικά n-2 συμπτύξεις (contractions) ακμών, αφού θέλουμε να μείνουν 2 κορυφές στο
# τέλος και σε κάθε σύμπτυξη φεύγει μια κορυφή.
for i in range(n-2):
EE = [] # λίστα με όλες τις ακμές μέσα, μια φορά την κάθε μια
for j in W.keys():
for v in W[j]:
if [v, j] not in EE: # δεν προσθέτουμε την ακμή στην ΕΕ αν έχει ήδη μπει με την ανάποδη
# σειρά κορυφών
EE.append([j, v])
E = len(EE) # E είναι ο αριθμός των ακμών
e = np.random.randint(0, E) # τυχαία ακμή
u = EE[e][0] # αρχική κορυφή της e
v = EE[e][1] # τελική κορυφή της e