Alberi

Un albero è un grafo non orientato, connesso e aciclico

Una foresta è un grafo non orientato e aciclico

Proprietà

Dato un grafo $G=(V,E)$, le seguenti affermazioni sono equivalenti:

• $G$ è un albero
• $G$ è aciclico e $|E| =|V|-1$
• $G$ è connesso e $|E| =|V|-1$
• ogni coppia di nodi di $G$ è connessa da un unico cammino
• $G$ è connesso ma se viene rimosso un qualsiasi arco da $E$ il grafo risultante è disconnesso
• $G$ è aciclico ma se viene aggiunto un qualsiasi arco ad $E$ il grafo risultante è ciclico

Albero ricoprente

Sia $G=(V,E)$ un grafo non orientato e connesso

Un albero ricoprente (spanning tree) di $G$ è un sottografo $T$ di $G$ tale che: $T$ è un albero che contiene tutti i nodi di $G$

Un grafo può avere più alberi ricoprenti

Minimum Spanning Tree Problem

Sia $G=(V,E)$ un grafo non orientato e connesso dove ad ogni arco $e_i \in E$ è associato un costo $c_i$

Il costo di un albero ricoprente $T$ di $G$ è dato dalla somma dei costi degli archi che lo compongono

Problema: determinare l’albero ricoprente di $G$ di costo minimo

Modello matematico 1: Subtour Elimination