Cut (teoria graficelor)
Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 11 august 2021; verificările necesită 2 modificări .Un grafic tăiat în problemele de curgere este o pereche de mulțimi de vârfuri (S,T) astfel încât
- , unde este mulțimea vârfurilor graficului
- , unde este sursa, este scurgerea.
Mărimea tăieturii este suma capacităților unor astfel de muchii care .
Alte definiții ale unei tăieturi (secțiuni) a unui grafic
- O tăietură grafică este un set de muchii care formează un subgraf bipartit , a cărui eliminare împarte graficul în două sau mai multe componente, care, în special, pot fi noduri izolate. La fel și o linie care trece prin toate marginile tăieturii graficului.
Caracteristici
- Liniile de secțiune pot traversa un număr arbitrar de muchii și coarde.
- Pentru a obține secțiunea principală a graficului, este necesar să trasați linia de secțiune a graficului în așa fel încât să intersecteze doar o ramură a graficului la o intersecție arbitrară a coardelor.