Salve a tutti, avrei bisogno di una mano con questi esercizi sui grafi.
1) Mostrare che se una foresta ha \(n\) vertici, \(m\) archi e \(c\) componenti connessi, allora \(n = m + c\)
2) Si supponga che un grafo \(G\) sia connesso e che per ogni suo arco l'eliminazione dell'arco stesso generi un grafo disconnesso. Dire che tipo di grafo è \(G\) e provarlo.
3) Si supponga che un multigrafo \(G\) non abbia cicli Euleriani. Scrivere un algoritmo che scelga il minimo numero di archi da aggiungere a \(G\) per ottenere un grafo \(G'\) che abbia un ciclo Euleriano. Provare che l'algoritmo è corretto ed analizzare la sua complessità.
4) Il grafo bipartito completo \(K_{n, m}\) ha \(m + n\) vertici. I vertici sono divisi in due gruppi \(A\), di dimensione \(n\), e \(B\), di dimensione \(m\). Per ogni vertice \(a \in A\) e \(b \in B\) esiste un arco \((a, b)\). Non esistono due vertici nello stesso gruppo collegati da un arco.
\(\hspace{1cm}\)a) Dare una caratterizzazione dei valori di \(m\) ed \(n\) in modo che \(K_{m, n}\) abbia un ciclo Euleriano.
\(\hspace{1cm}\)b) Dare una caratterizzazione dei valori di \(m\) ed \(n\) in modo che \(K_{m, n}\) abbia un ciclo Hamiltoniano.
5) Si consideri il seguente algoritmo che costruisce un TSP-tour per un'istanza \((G(V, E), w)\) di TSP-metrico. L'algoritmo estende un circuito iniziale che passa per due soli vertici, a un circuito finale che passa per tutti i vertici, aggiungendo un nuovo vertice per volta. Il nuovo vertice è il più vicino al circuito parziale già costruito, tra tutti quelli non ancora inclusi, ed è aggiunto al fine di indurre la minima crescita possibile.
\(\hspace{1cm}\)1. Si parte con un arco \((i, j)\) di peso minimo
\(\hspace{1cm}\)2. Setta \(C = i, j, i\) (il circuito che passa per \(i\) e \(j\))
\(\hspace{1cm}\)3. \(for\) \(i = 3, ..., n\)
\(\hspace{1cm}\)4. Scegli \(v \in V \setminus C\) tale che \(min_{u \in C}\) \(w(v, u)\) sia il minimo tra tutte le possibili scelte di \(v\)
\(\hspace{1cm}\)5. Scegli una coppia di vertici consecutivi \(u, u'\) in \(C\) tale che \(d(u, v) + d(v, u') - d(u, u')\) sia minimo
\(\hspace{1cm}\)6. Aggiungi \(v\) a \(C\) tra \(u\) e \(u'\), e indicando con \(C^{new}\) il nuovo ciclo avremo quindi
\(\hspace{1cm}\)\(w(C^{new}) = w(C) - d(u, u') + d(u, v) + d(v, u')\)
Provare che l'algoritmo è 2-approssimato per TSP-metrico.