Esercizio - Numero di tagli minimi di un grafo, dimostrazione e casi estremi

Testo (domanda da orale).

1. Dimostrare che un multigrafo con $n$ vertici ha al più $\binom n2$ tagli minimi.
2. Dire quale grafo raggiunge il limite e contare i tagli minimi di: il ciclo $C_6$; il cammino con $6$ vertici; la stella con centro e $5$ foglie; il grafo completo $K_5$; il grafo bipartito completo $K_{3,3}$; i due triangoli collegati da un ponte ($6$ vertici).
3. Verificare i conteggi enumerando tutte le bipartizioni.

Teoria: Taglio minimo randomizzato - algoritmo di KargerTaglio minimo globale di un multigrafo con n vertici. Algoritmo di Karger: finché restano più di 2 vertici, scegliere un arco uniformemente tra i rimasti e contrarlo (fondere gli estremi, tenere i paralleli, togliere i cappi); gli archi tra i due supervertici finali sono un taglio. Un taglio minimo C di k archi sopravvive se nessun suo arco viene contratto; con n_i vertici il grado minimo è ≥ k, quindi |E_i| ≥ n_i k/2 e Pr[contrarre un arco di C] ≤ 2/n_i; il prodotto telescopico dà Pr[output = C] ≥ 2/(n(n-1)) = 1/C(n,2). Con t = C(n,2) ln(1/δ) ripetizioni indipendenti il fallimento è ≤ δ. Corollario: un grafo ha al più C(n,2) tagli minimi (stretto per il ciclo). Karger-Stein: contrarre fino a n/√2+1 vertici (sopravvive con prob ≥ 1/2) e ricorrere due volte, T(n) = O(n² log n), successo Ω(1/log n).Taglio minimo randomizzato - algoritmo di Karger → (corollario sul numero di tagli minimi).

Soluzione

Punto 1. Sia $k$ il taglio minimo e siano $C_1,\dots,C_r$ i tagli minimi distinti. Per il teorema di Karger, l'algoritmo restituisce proprio $C_j$ con probabilità $p_j\ge\frac2{n(n-1)}=1/\binom n2$. Gli eventi «l'output è $C_j$» sono a due a due disgiunti (l'output è un solo taglio). Quindi $$1\ge\sum_{j=1}^rp_j\ge\frac r{\binom n2}\quad\Longrightarrow\quad r\le\binom n2 .$$ Il risultato dice che, anche se i tagli possibili sono $2^{n-1}-1$, quelli minimi sono pochi.

Punto 2. Il limite è raggiunto dal ciclo, che ha $\binom n2$ tagli minimi (le coppie di archi), tutti di dimensione $2$; gli altri grafi dell'elenco ne hanno molti meno.

• $C_6$: $\binom62=15$ tagli minimi, di dimensione $2$ (uno per ogni coppia di archi).
• Cammino con $6$ vertici: ha $5$ archi, ognuno è un ponte e un taglio di dimensione $1$: $5$ tagli minimi ($\le15$).
• Stella con $5$ foglie: $5$ tagli minimi (uno per foglia, dimensione $1$).
• $K_5$: il grado è $4$, il taglio minimo è $4$ e sono minimi i tagli a vertice singolo: $5$ tagli ($\le10$). Un taglio $2+3$ ha $6$ archi.
• $K_{3,3}$: grado $3$, taglio minimo $3$, tagli a vertice singolo: $6$ tagli ($\le15$).
• Due triangoli con ponte: il ponte è l'unico taglio di dimensione $1$: $1$.

In generale un albero con $n$ vertici ha $n-1$ tagli minimi (uno per arco, ciascuno un ponte).

Punto 3. Enumerando le $2^{n-1}-1$ bipartizioni (con l'ultimo vertice sempre nel lato 0) e contando gli archi tagliati, un programma trova: $C_6$: dimensione $2$ e $15$ tagli; cammino: $1$ e $5$; stella: $1$ e $5$; $K_5$: $4$ e $5$; $K_{3,3}$: $3$ e $6$; due triangoli: $1$ e $1$. Per $K_4$: $3$ e $4$.

Risultati: limite $\binom n2$ dimostrato con eventi disgiunti; $15,\ 5,\ 5,\ 5,\ 6,\ 1$ nell'ordine dell'elenco; il ciclo raggiunge il limite.

from itertools import combinations
def tagli_minimi(n, E):
    miglior, conteggio = None, 0
    for m in range(1, 2**(n - 1)):                    # il vertice n-1 resta sempre nel lato 0
        d = sum(((m >> u) & 1) != ((m >> v) & 1) for u, v in E)
        if miglior is None or d < miglior: miglior, conteggio = d, 1
        elif d == miglior: conteggio += 1
    return miglior, conteggio
ciclo = [(i, (i + 1) % 6) for i in range(6)]
print(tagli_minimi(6, ciclo))                                                     # (2, 15)
print(tagli_minimi(6, [(i, i + 1) for i in range(5)]))                            # (1, 5)
print(tagli_minimi(6, [(0, i) for i in range(1, 6)]))                             # (1, 5)
print(tagli_minimi(5, list(combinations(range(5), 2))))                           # (4, 5)
print(tagli_minimi(6, [(a, b) for a in range(3) for b in range(3, 6)]))           # (3, 6)
print(tagli_minimi(6, [(0, 1), (0, 2), (1, 2), (3, 4), (3, 5), (4, 5), (2, 3)]))  # (1, 1)