graph cuts

Complete

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

S=fa;b;cgabcdef

Disjoint set

a2Sc2Sabcd

Component in a forest

S=fa;bgabcd