graph cuts
Summary
Simple check for cut edges
| Endpoint | Endpoint | Is |
|---|---|---|
| in | in | no: internal edge |
| in | outside | yes |
| outside | in | yes: same undirected edge |
| outside | outside | no: external edge |
Useful properties
Concept
Graph Cut
- for a chosen subset of vertices
, in undirected graphs - set of all edges with exactly one endpoint in
cuts refer to edges leaving the subset not the vertices
Standard cut
Disjoint set
Component in a forest