[ESAME] 7 luglio 2023 es4

[Frisbon]

[Frisbon]

Il costo non viene specificato, soluzione naive:
Definisco Kruskal che restituisce un MST dato un grafo (banale)

def es4(G,arco):
    K1 = Kruskal(G)
    if arco not in K1: return "YES"
    K2 = Kruskal(G senza arco)
    
    if len(V(K1)) == len(V(K2)):
        return "YES"
    return "NO"

[Elia-Belli]

Il fatto che i sottografi risultanti abbiano un numero diverso di nodi è condizione sufficiente ma non necessaria affinché il secondo sottografo non sia un MST, ciò avviene solamente quando l'arco rimosso sconnette $G$ ovvero è un ponte.
Nel caso in cui l'arco rimosso fosse fondamentale per ottenere un albero di copertura di costo minimo con l'attuale controllo l'MST sarebbe dato per buono, quindi dobbiamo controllare anche che i pesi degli MST siano uguali.

[CasuFrost]

Dato che tutti gli $MST$ di un grafo hanno lo stesso peso, esisterà un $MST$ di $G$ senza $(x,y)$ se e solo se

$$w(MST(G))=w(MST(G- {(x,y)}))$$