Grafo & città

[Hydr]

Salve!
Giusto per provare, mi sono iscritto a un concorso scolastico a carattere logico.
Ecco un problema di esercitazione proposto. Non avendo ancora studiato nulla del genere, mi piacerebbe vedere il procedimento risolutivo di questo:

Il grafo in figura rappresenta una rete di trasporti tra le città c1, …, c6. Ogni freccia tra due città è etichettata
dal valore massimo di passeggeri che è possibile trasportare tra le due città. I passeggeri possono anche
essere divisi tra una città e l’altra; ad esempio, se mandiamo sette passeggeri tra c1 e c2, questi poi possono
essere divisi a piacere, rispettando il valore massimo: uno può andare a c3, quattro a c5 e i restanti due a c4.
Qual è il valore massimo di passeggeri che è possibile far viaggiare da c1 a c6?

[@melia]

Credo che siano 19.
Da C1 ne mando 4 in C3, 7 in C2 e 8 in C4.
Dei 7 arrivati in C2, 2 li mando in C3 e gli altri 5 in C5.
Degli 8 arrivati in C4, 2 li mando in C5 e 6 in C6, e i primi 6 sono arrivati.
Adesso in C5 ce ne sono 7 che possono andare tutti in C6, e altri 7 sono arrivati.
In C3 ce ne sono 6, che possono andare tutti in C6.
In totale $6+7+6=19$

[Hydr]

Buonasera e grazie!
Penso di aver capito il problema, ora.

Fra l'altro, credo basti sommare i valori dei primi tre trasporti $ 4, 7, 10 $ stando attenti al fatto che non rimagano incastrati.
$ 10 > 6 + 2 => 8 $

$ 4 + 7 + 8 = 19 $, che corrisponde!

[@melia]

È da quello che sono partita togliendo poi i due che restavano incastrati in $c_4$

[giuspeppe94]

Se sei curioso e non hai paura di nomi strambi, puoi vedere il teorema max-flow min-cut. Quello che tu cerchi è proprio il max-flow da c1 a c6, per questo teorema è uguale al min-cut per c1 e c6, ovvero il minimo peso degli archi che bisogna togliere al grafo per far sì che non sia più possibile arrivare da c1 a c6. Chiaramente questo lo puoi fare in molti modi, ma se cerchi di farlo togliendo complessivamente un costo più piccolo possibile, hai il min-cut. Nel nostro caso devi togliere almeno 19, da cui la tesi (togli 19 con c1c2, c1c3, c4c5, c4c6).

https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem