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 p≤n, una p-partizione di G è una partizione dell'insieme V in p componenti non nulle V₁, ..., V_p, tali che il sottografo indotto di G da ogni componente V_k 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);
}

Corso di Ottimizzazione Combinatoria (IN440)

Esercizi e sorgenti dei programmi

Partizionamento di un albero in p componenti connesse

Partizionamento di un albero in `p` componenti connesse