Maximum matching e numero d'archi
Ciao a tutti!
Volevo farvi una domanda su un esercizio che dice:
G grafo con n certici. Supponiamo che G ha un maximum matching con k archi.
Qual è il massimo numero di archi di G se:
a) n=2k
b) n=2k + 2
Posso supporre G grafo completo? perché di per sé è il grafo con il maggior numero di archi..
E poi andrei per induzione..
Che dite voi?
Grazie anticipatamente per il tempo dedicato a questo quesito
Volevo farvi una domanda su un esercizio che dice:
G grafo con n certici. Supponiamo che G ha un maximum matching con k archi.
Qual è il massimo numero di archi di G se:
a) n=2k
b) n=2k + 2
Posso supporre G grafo completo? perché di per sé è il grafo con il maggior numero di archi..
E poi andrei per induzione..
Che dite voi?
Grazie anticipatamente per il tempo dedicato a questo quesito
Risposte
risolto, forse in modo non troppo formale ma fatto
Proponicelo così pure io imparo due cose sui grafi 
per n=2k
Considero il grafo completo $K_N$ perché è il grafo con più archi possibile avendo n vertici, e questo ammette un perfect matching con n/2 archi (per com'è fatto)
allora il numero cercato è il numero di archi di $K_n$, cioè $n(n-1)/2$, sostituisci con le k, e si trova $k(2k-1)$
per n=2k+2
invece devi cercate un altro grafo, perché $K_n$ avrebbe un perfect matching non con k ma con k+1 archi.
Cercando un po' si trova che il grafico "buono" è $K_(n-1) + {v}$ dove v è un vertice isolato.
Si capisce?
Considero il grafo completo $K_N$ perché è il grafo con più archi possibile avendo n vertici, e questo ammette un perfect matching con n/2 archi (per com'è fatto)
allora il numero cercato è il numero di archi di $K_n$, cioè $n(n-1)/2$, sostituisci con le k, e si trova $k(2k-1)$
per n=2k+2
invece devi cercate un altro grafo, perché $K_n$ avrebbe un perfect matching non con k ma con k+1 archi.
Cercando un po' si trova che il grafico "buono" è $K_(n-1) + {v}$ dove v è un vertice isolato.
Si capisce?
Grazie mille.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo