Esercizio 1

Determinare la complessità in tempo dell'algoritmo (descritto a lezione) per il calcolo di un matching massimo in un grafo.

Esercizio 2

Dato un grafo G=(V,E), indichiamo con w la dimensione della sua più grande cricca indotta e con χ il minimo numero di colori che permette di colorare G.

E' banale dimostrare che w è sempre minore o uguale a χ. Inoltre il grafo C₅ (il ciclo semplice con 5 vertici) ha w=2 e χ=3 quindi, in questo grafo, w<χ.

Trovare un grafo per cui w<<χ.