[ESAME] 12 gennaio 2023 es4

[Frisbon]

tengo a precisare che sulla traccia originale ha scritto 2016, si è sbagliato, è del 2023.

[Frisbon]

def Risparmia(SOL,VIS,COSTR,G,nodo): #visita solo se esistono colori alternati
    VIS[nodo] = 1;
    for adiacente in nodo:
        if VIS[adiacente] == 0 and adiacente.colore != nodo.colore:
            SOL.add(( nodo, adiacente) ) #aggiungi arco
            Risparmia( SOL, VIS, G, adiacente)
        else:
            COSTR.add(nodo) #aggiungo il nodo costretto
    return VIS
    

def Costretto(SOL,VIS,G,nodo): # visita qualsiasi cosa, se costretto
    VIS[nodo] = 1;
    for adiacente in nodo:
        if VIS[adiacente] == 0:
            SOL.add(( nodo, adiacente) ) #aggiungi arco
            VIS = Risparmia( SOL, VIS, G, adiacente) #ricomincia a "risparmiare"
    return VIS

def es(G,nodo):
    VIS = [0,...,0]; SOL = {}; COSTR = {}
    while 0 in VIS: #fino a quando non visito tutti
        VIS = Risparmia(SOL,VIS,G,nodo)
        for x in COSTR:
            VIS = Costretto(SOL,VIS,G,x)

[Frisbon]

Nota, ho trovato che Exyss ha negli appunti una soluzione molto ma molto più corta....

[cornflexxx]

Praticamente identico a #93 l'unica differenza è che qui aggiungiamo per primi gli archi $(u,v)$ tali che $C(u) \neq C(v)$.

[CarloDaRomadev]

//algoritmo greedy
//MODIFICO L'ALGORITMO DI PRIM
def albero_colorato(G){
        sol = []
	vis = [0,...,0]
	while exists w in V(G) | vis[w] == 0{
		if exists (v,u) = arco in E(G) | (v.colore != u.colore && vis[u] == 0 && vis[v] == 1){
			sol.append(v,u)
		}
		else{
			(v,u) = arco in E(G)| (vis[u] == 0 && vis[v] == 1)
			sol.append(v,u)
		}
	}
}
return sol

/* 
costo finale = O(nm) 
   dato che il ciclo while è ripetuto m volte mentre le operazioni interne al ciclo costano O(2m).
*/

[CiottoloMaggico]

Algoritmo di Prim che utilizza la funzione w per il peso degli archi