Taglio (teoria dei grafi)
nella teoria dei grafi, partizione dei vertici in due sottinsiemi disgiunti / Da Wikipedia, l'enciclopedia encyclopedia
Caro Wikiwand AI, Facciamo breve rispondendo semplicemente a queste domande chiave:
Puoi elencare i principali fatti e statistiche su Taglio (teoria dei grafi)?
Riassumi questo articolo per un bambino di 10 anni
MOSTRA TUTTE LE DOMANDE
Nella teoria dei grafi, un taglio è una partizione dei vertici di un grafo in due sottoinsiemi disgiunti.
Ogni taglio determina un insieme di taglio (o cut-set), definito come l'insieme degli archi che hanno i propri estremi nei due sottinsiemi della partizione. In un grafo connesso, ogni cut-set è relativo ad un unico taglio.
In una rete di flusso, un taglio s-t è un taglio tale che il vertice sorgente (s) ed il pozzo (t) non appartengano allo stesso sottinsieme della partizione. La capacità di un taglio s-t è definita come la somma delle capacità degli archi appartenenti al cut-set.