Πρόβλημα: Έχουμε $n$ πόλεις και κάθε μια από αυτές συνδέεται με κάθε άλλη με ένα δρόμο. Θέλουμε να χρωματίσουμε όλους αυτούς τους δρόμους με δύο χρώματα, κόκκινο ή μπλε ας πούμε, ώστε να έχουμε μικρό αριθμό από μονοχρωματικά τρίγωνα, τριάδες δηλ. $i, j, k$ από διαφορετικές πόλεις που οι μεταξύ τους 3 δρόμοι να έχουν όλοι βαφεί με το ίδιο χρώμα.
Είναι πολύ εύκολο να πετύχουμε πολλά μονοχρωματικά τρίγωνα (π.χ. βάφουμε όλους τους δρόμους μπλε) αλλά καθόλου προφανές του πώς να πετύχουμε λίγα μονοχρωματικά τρίγωνα. Ισχύει όμως το παρακάτω το οποίο και αποδείξαμε στο μάθημα:
Θεώρημα Υπάρχει χρωματισμός με δύο χρώματα με $\le \frac14 \binom{n}{3}$ μονοχρωματικά τρίγωνα.
Δώσαμε μια απόδειξη αυτού που χρησιμοποιεί τυχαίους χρωματισμούς. Αν δηλ. επιλέξουμε το χρώμα του κάθε δρόμου να είναι με ίση πιθανότητα μπλέ ή κόκκινο, ανεξάρτητα για όλους τους δρόμους, προκύπτει μετά από ένα εύκολο υπολογισμό ότι ο μέσος αριθμός μονοχρωματικών τριγώνων είναι $\frac14\binom{n}{3}$, άρα υπάρχει έκβαση του πειράματος με το πολύ τόσα μονοχρωματικά τρίγωνα.
Δείτε τις λεπτομέρειες εδώ
Παρακάτω βλέπετε μια απλή υλοποίηση σε python του πιθανοθεωρητικού αυτού αλγορίθμου. Βάφουμε τους δρόμους στην τύχη και μετά μετράμε πόσα μονοχρωματικά τρίγωνα έχουμε (και τυπώνουμε και τον αριθμό $\frac14\binom{n}{3}$ για σύγκριση). Αν τον τρέξετε αυτό τον αλγόριθμο μερικές φορές (για το ίδιο $n$) θα δείτε ότι τις περισσότερες φορές βγάζει αριθμό κάτω από το $\frac14\binom{n}{3}$ αλλά όχι πάντα.
import numpy as np
n=50 # αριθμός πόλεων
color = np.zeros((n, n))
for i in range(n):
for j in range(i): # για το δρόμο από την πόλη i στην πόλη j
color[i][j] = color[j][i] = np.random.randint(0, 2) # Επιλέγουμε στην τύχη το χρώμα κάθε δρόμου
count = 0 # πόσα μονοχρωματικά τρίγωνα έχουμε
for i in range(n): # Με το τριπλό αυτό loop απαριθμούμε όλα τα τρίγωνα i, j, k (με i<j<k)
for j in range(i+1, n):
for k in range(j+1, n):
if color[i][j] == color[j][k] and color[j][k] == color[i][k]:
count += 1 # Αν είναι μονοχρωματικό αυξάνουμε τον μετρητή
print(f"Βρήκαμε {count} μονοχρωματικά τρίγωνα")
all=n*(n-1)*(n-2)/6
print(f"Επί συνόλου {all} τριγώνων")
print(f"Ένα τέταρτο είναι {all/4}")
Έπειτα είδαμε ότι υπάρχει μια, αρκετή γενική, μέθοδος για να μετατρέψει κανείς έναν τέτοιο πιθανοθεωρητικό αλγόριθμο σε ντετερμινιστικό, χωρίς τη χρήση δηλ. πιθανοτήτων.
Η μέθοδος που δείξαμε ονομάζεται μέθοδος των δεσμευμένων πιθανοτήτων ή των δεσμευμένων μέσων τιμών και αυτό που κάνουμε είναι ότι δίνουμε χρώμα στις ακμές μας μια προς μια προσέχοντας κάθε φορά να μη χειροτερεύουμε (μεγαλώνουμε) τη μέση τιμή του πλήθους μονοχρωματικών τριγώνων δεσμευμένο υπό τον τρέχοντα μερικό χρωματισμό.
Μπορείτε να διαβάσετε τη μέθοδο εδώ στο Θεώρημα 3.1 και 3.2.
Έπειτα φτιάξαμε το σκελετό για το πρόγραμμα που θα υλοποιεί αυτό τον ντετερμινιστικό αλγόριθμο. Το input είναι μόνο ο φυσικός αριθμός $n$ και το πρόγραμμα θα πρέπει να παράγει ένα χρωματισμό των $\binom{n}{2}$ ακμών του πλήρους γραφήματος $K_n$ με το πολύ $\frac14\binom{n}{3}$ μονοχρωματικά τρίγωνα.
Άσκηση Παρακαλώ συμπληρώστε το παρακάτω πρόγραμμα ώστε να είναι ένα πλήρες και σωστό πρόγραμμα σε python. Δείτε τα σχόλια μέσα στο πρόγραμμα για οδηγίες. Αν θέλετε μπορείτε να δουλέψετε σε ομάδες, αλλά όχι να αντιγράψετε κώδικα από τη μια ομάδα στην άλλη.
n = int(input("Δώστε το n: "))
k = n*(n-1)//2
C = k*[0] # Στη λίστα C το 0 σημαίνει τυχαίο χρώμα, 1=κόκκινο, 2=μπλε
L = [] # Ποιες είναι οι κορυφές της υπ' αριθμόν i ακμής
for i in range(n):
for j in range(i+1, n):
L.append((i, j))
def prob_mono(i, j, k, C):
"""
Επιστρέφει την πιθανότητα το τρίγωνο i, j, k να είναι
μονοχρωματικό αν ισχύει ο μερικός χρωματισμός C
"""
def mean_under_colors(C):
"""
Υπολογίζει τη μέση τιμή του X υπό τη δέσμευση του μερικού
χρωματισμού C
"""
for i in range(k): # Για όλες τις ακμές i
u = L[i][0]
v = L[i][1] # αυτές είναι οι κορυφές της i ακμής
# Πρέπει να διαλέξω το χρώμα της ακμής i
C1 = C[:] ; C1[i]=1 # O C1 είναι ο μερικός χρωματισμός που προκύπτει από τον C αν θέσουμε την i ακμή στο χρώμα 1
C2 = C[:] ; C2[i]=2 # Ομοίως για τον C2
value1 = mean_under_colors(C1) # Υπολογίζετε εδώ τη μέση τιμή υπό τον ένα και τον άλλο χρωματισμό
value2 = mean_under_colors(C2)
# Επιλέξτε το χρώμα που δίνει τη μικρότερη τιμή παραπάνω και ενημερώστε το μερικό χρωματισμό C
# Τυπώστε πόσα μονοχρωματικά τρίγωνα έχει ο χρωματισμός που βρήκατε (και τον αριθμό 1/4 (n ανά 2) για σύγκριση)
Ο τρόπος που είναι γραμμένο το τελευταίο for loop στον κώδικα παραπάνω είναι πολύ πιο αργός απ' ό,τι χρειάζεται. Κάθε φορά υπολογίζει τη δεσμευμένη μέση τιμή καλώντας τη συνάρτηση mean_under_colors η οποία για να τρέξει θέλει χρόνο της τάξης του $n^3$ (όσα είναι όλα τα τρίγωνα). Στην πραγματικότητα το μόνο που μας ενδιαφέρει είναι ποιο χρώμα από τα δύο που εξετάζουμε να δώσουμε στην τρέχουσα κορυφή θα δώσει μικρότερη μέση τιμή. Άρα μας αρκεί να υπολογίζουμε τη διαφορά των δύο δεσμευμένων μέσων τιμών (μια για κόκκινο, μια για μπλέ). Στη διαφορά όμως η συνεισφορά των περισσότερων τριγώνων εξαφανίζεται και μένουν μόνο $O(n)$ τρίγωνα να υπολογιστούν, μια σημαντική επιτάχυνση.
Αφού φτιάξετε τον παραπάνω κώδικα όπως προτείνεται εκεί μέσα διορθώστε τον ώστε να τρέχει και πιο γρήγορα όπως εξηγείται στην προηγούμενη παράγραφο.