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 C5 (il ciclo semplice con 5 vertici) ha w=2 e χ=3 quindi, in questo grafo, w<χ.
Trovare un grafo per cui w<<χ.