[Algoritmi] Esercizi teoria dei grafi

Messaggioda NightWnvol » 04/11/2018, 23:58

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.
Ultima modifica di NightWnvol il 07/11/2018, 13:19, modificato 2 volte in totale.
NightWnvol
Starting Member
Starting Member
 
Messaggio: 19 di 42
Iscritto il: 18/05/2017, 17:44

Re: [Algoritmi] Esercizi teoria dei grafi

Messaggioda apatriarca » 05/11/2018, 21:22

In cosa incontri difficoltà? Hai qualche idea di come si possano risolvere? Per il primo esercizio hai ad esempio che una foresta è una unione disgiunta di alberi e ogni albero è connesso per cui hai che \(c\) è il numero di alberi nella foresta. Che relazione c'è tra il numero di vertici e archi in un albero? Se ora consideri \(c\) alberi, come cambia questa relazione?
apatriarca
Moderatore
Moderatore
 
Messaggio: 5143 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: [Algoritmi] Esercizi teoria dei grafi

Messaggioda NightWnvol » 06/11/2018, 14:06

Sto incontrando difficoltà soprattutto nelle dimostrazioni delle soluzioni che trovo.
Per quanto riguarda il primo esercizio ho ragionato così:

1) La relazione tra \(n\) vertici e \(m\) archi di un albero è \(m = n - 1\), quindi \(n = m + 1\). Il caso banale è dato da una foresta formata da un singolo albero con un solo vertice, quindi la relazione \(n = m + c\) è verificata dato che \(n = 1\), \(m = 0\), \(c = 1\). Considerando ora una foresta con due alberi \(c_1\) e \(c_2\) rispettivamente con \(n_1\) ed \(n_2\) vertici, avremo che \(n = n_1 + n_2\), quindi \(n = m_1 + c_1 + m_2 + c_2 = m + c\).

Per il secondo:
2) Se per ogni arco di \(G\) la cancellazione dello stesso genera un grafo disconnesso, allora \(G\) è un albero. Una possibile dimostrazione potrebbe essere che se \(G\) contiene dei cicli (e quindi non è un albero) allora l'eliminazione di uno degli archi che compone il ciclo non genererebbe un grafo disconnesso. (Giusto?)

Per gli altri esercizi ci sto lavorando, qualche idea da dove partire?
NightWnvol
Starting Member
Starting Member
 
Messaggio: 20 di 42
Iscritto il: 18/05/2017, 17:44

Re: [Algoritmi] Esercizi teoria dei grafi

Messaggioda apatriarca » 07/11/2018, 01:01

No, due alberi avranno \(n = m + 2\) vertici. Se vuoi usare l'induzione allora va bene partire con un singolo albero (o anche nessuno), ma poi devi considerare una foresta con \(k-1\) componenti connesse e vuoi aggiungere ad esso un albero/componente connessa.

Per quanto riguarda il punto 2, hai dimostrato che se il grafo non è aciclico allora non rispetta la tua condizione. Ti manca dimostrare che se è un albero allora l'eliminazione di un suo arco porta ad un grado disconnesso. E' abbastanza ovvio ma dovresti almeno scrivere tale parte per completezza.

Riguardo agli altri punti.. Hai qualche idea su come creare un ciclo euleriano per esempio?
apatriarca
Moderatore
Moderatore
 
Messaggio: 5144 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: [Algoritmi] Esercizi teoria dei grafi

Messaggioda NightWnvol » 07/11/2018, 14:11

Non so se ho ben capito la dimostrazione per il primo esercizio. Considerando \(c -1\) componenti connesse e volendone aggiungere una nuova significa che devo considerare \(n = m + c - 1 + 1\), giusto?

Gli esercizi 3 e 4:
3) Condizione necessaria per far si che un multigrafo (non orientato) abbia un ciclo Euleriano, è che il numero di archi incidenti in ogni vertice \(v\) sia pari, ovvero \(d(v)\) è pari \(\forall v \in V\). L'algoritmo che ho pensato è questo:

1. per ogni \(v \in V\) {
2. \(\hspace{0.5cm}\)se \(d(v)\) è dispari {
3. \(\hspace{1cm}\)trova un vertice \(u\) tale che \(d(u)\) sia dispari
4. \(\hspace{1cm}\)aggiungi l'arco \((v, u)\) a \(G'\)
5. \(\hspace{0.5cm}\)}
6. }
7. ritorna \(G'\)

La complessità è \(O(n)\). Come faccio ora a dimostrare la correttezza dell'algoritmo?

4)
a) Per avere un ciclo Euleriano \(m\) ed \(n\) devono essere entrambi di numero pari.
b) Per avere un ciclo Hamiltoniano si deve avere che \(m = n\) con \(n,m > 1\).
NightWnvol
Starting Member
Starting Member
 
Messaggio: 21 di 42
Iscritto il: 18/05/2017, 17:44

Re: [Algoritmi] Esercizi teoria dei grafi

Messaggioda apatriarca » 08/11/2018, 09:03

1. Sia \(n_c\) il numero di vertici nella tua foresta con \(c\) componenti connesse e \(m_c\) il numero di archi. Hai che un albero ha \(n_1 = m_1 + 1\) vertici. La loro somma sarà quindi
\[n_{c+1} = n_c + n_1 = m_c + c + m_1 + 1 = m_{c + 1} + c + 1. \]

La complessità del tuo algoritmo \(3\) non è \(O(n)\) nel modo in cui l'hai descritto. La ricerca di un vertice nella riga \(3\) è infatti lineare se fatta in modo naive. E' tuttavia certamente vero che è possibile implementarlo in modo che la complessità sia lineare facendo qualcosa come segue (simil python):
Codice:
vs = [v for v in V if d(u) % 2 == 1]
G += zip(vs[0::2], v[1::2])

In altre parole prendi tutti i vertici con grado dispari e crei un arco tra coppie consecutive. Credo che tu possa dimostrarne la correttezza dimostrando che qualsiasi algoritmo che crea un grafo con cicli Euleriani deve creare almeno quel numero di archi. Fare cioè in modo che ogni vertice con grado dispari abbia un solo arco aggiuntivo.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5145 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite