Esercizi e sorgenti dei programmi

Partizionamento di un albero in p componenti connesse

Dato un albero T=(V,E) si chiede di stampare tutte le partizioni dell'insieme V in p componenti connesse.

Assegnato un grafo G=(V,E) ed un intero pn, una p-partizione di G è una partizione dell'insieme V in p componenti non nulle V1, ..., Vp, tali che il sottografo indotto di G da ogni componente Vk della partizione sia connesso.

Per produrre una p-partizione di un albero (e di un cammino, che è un caso particolare di un albero) è sufficiente rimuovere esattamente p-1 spigoli, ottenendo in questo modo p sotto-alberi non nulli. Il problema si riduce quindi al calcolo di tutte le possibili assegnazioni dei p-1 "tagli" agli n-1 spigoli dell'albero. Tali assegnazioni corrispondono a tutte le possibili scelte ordinate (combinazioni senza ripetizioni) di p-1 spigoli dall'insieme E(T).

Di seguito riportiamo il programma in C dell'algoritmo per il calcolo di tutte le p-partizioni di un albero T con n vertici. Per rappresentare l'albero, invece di usare le liste di adiacenza, è stato utilizzato il vettore padre[i] che, per ogni vertice i dell'albero, indica il vertice "padre". L'algoritmo implementato dal programma, per semplicità, assume che la radice dell'albero sia sempre il vertice 1 e che da tale vertice (privo di padre, padre[1]=-1), gli spigoli siano orientati secondo l'orientazione "naturale". La compilazione del programma richiede l'uso della libreria grafi.c.

/* ** ppartizioni.c ** ** p-partizione in componenti connesse di un albero $T$ assegnato. ** Dato un intero p>0 e un albero T=(V,E), con |V| = n >= p, si ** devono produrre tutte le partizioni di T in p sottoalberi non ** vuoti. ** ** #(@) 20081217 (liverani@mat.uniroma3.it) */
#include <stdlib.h> #include <stdio.h> #include "grafi.h" #define MAX 100
/* * leggiAlbero(padre[]) * * L'albero viene memorizzato tenendo conto, per ogni vertice, * del vertice padre. */
int leggiAlbero(int padre[]) { int n, i; printf("Inserimento dell'albero (con radice in 1)\n"); printf("Numero di vertici dell'albero: "); scanf("%d", &n); for (i=1; i<=n; i++) padre[i] = -1; for (i=1; i<=n; i++) { printf("Padre del vertice %d: ", i); scanf("%d", &padre[i]); } return(n); }
/* * stampaSottoalbero(padre[], t[], p, n, v) * * Stampa i vertici del sottoalbero con radice in v, delimitato dal * basso dai p tagli t[i]. L'algoritmo adottato e' inefficiente a causa * della rappresentazione banale dell'albero con il vettore dei vertici * "padre[i]" che obbliga ad eseguire un ciclo di n iterazioni per * individuare i figli del vertice "v". */
void stampaSottoalbero(int padre[], int t[], int p, int n, int v) { coda Q; int i; Q.primo = NULL; Q.ultimo = NULL; push(&Q, v); printf("{ "); while (Q.primo != NULL) { v = pop(&Q); printf("%d ", v); for(i=1; i<=n; i++) { if (padre[i] == v && t[i] == 0) { push(&Q, i); } } } printf("} "); return; }
/* * stampaPartizione(padre[], c[], p, n) * * Stampa le p componenti della partizione dell'albero * definita dai tagli c[i]=1 */
void stampaPartizione(int padre[], int c[], int p, int n) { int i, t[MAX]; for (i=1; i<=n; i++) t[i] = 0; for (i=2; i<=p; i++) t[c[i]] = 1; stampaSottoalbero(padre, t, p, n, 1); for (i=2; i<=p; i++) stampaSottoalbero(padre, t, p, n, c[i]); printf("\n"); return; }
/* * partizioni(padre, n, p) * * Calcola tutte le combinazioni semplici di n-1 spigoli * in classi di p-1 elementi: ogni combinazione di spigoli * corrisponde ad una combinazione di p-1 tagli assegnati * agli spigoli della combinazione; a sua volta tale combinazione * di tagli corrisponde ad una p-partizione in componenti * connesse degli n vertici dell'albero. */
void partizioni(int padre[], int n, int p) { int i, j, c[MAX]; for (i=2; i<=p; i++) { c[i] = i; } stampaPartizione(padre, c, p, n); i = p; while (i>1) { i = p; while (i>1 && c[i] == n-(p-i)) i--; if (i>1) { c[i]++; for (j=i+1; j<=p; j++) { c[j] = c[j-1]+1; } stampaPartizione(padre, c, p, n); } } return; }
/* * Funzione principale */
int main(void) { int padre[MAX], n, p; n = leggiAlbero(padre); printf("Inserisci il numero di componenti delle partizioni (1 < p < %d): ", n+1); scanf("%d", &p); partizioni(padre, n, p); return(0); }