Node Cut Size Calculator

Calculator

Example data table

Use the “Load sample graph” button to paste the first row automatically.

Formula used

The node cut size between two nodes s and t is the smallest number of intermediate vertices whose removal eliminates every path from s to t.

By a max-flow/min-cut interpretation of Menger’s theorem, the minimum node cut equals the maximum number of internally node-disjoint s-t paths.

To compute it, each vertex v is split into v_in and v_out with a capacity-1 edge v_in → v_out (capacity infinite for s and t). Original graph edges become infinite-capacity edges u_out → v_in. The min-cut value of this flow network is the node cut size.

How to use this calculator

1. Choose Between two nodes for a specific s → t cut, or Global connectivity for an overall minimum.
2. Paste edges, one per line, using labels like A B or A -> B.
3. Optionally list nodes; otherwise they are inferred from edges.
4. Select directed or undirected behavior and enter s and t if needed.
5. Press Compute to show results above this form.
6. Use Download CSV or Download PDF to export the last result.

Professional article

1) Why node cuts matter in physical networks

Many physics systems map cleanly onto graphs: diffusion pathways in porous media, transport links in microchannels, or routing in distributed sensor arrays. A node cut size tells you how many key sites must fail before transfer between two locations stops. It also helps connect topology changes to robustness and percolation thresholds.

2) Vertex cuts and real failure mechanisms

Failures often occur at junctions: clogged pores, overheated hubs, saturated detectors, or broken relays. A minimum vertex cut identifies the smallest set of intermediate nodes whose removal blocks every path, giving a direct fragility indicator for localized damage.

3) Flow-based computation and scaling

The calculator splits each node into an input and output linked by capacity 1. That capacity models one removable vertex. Original links become very large-capacity connections, so the max flow equals the maximum number of internally node-disjoint paths. Dinic’s method handles dozens of nodes and hundreds of edges interactively. Global mode may run many pairwise evaluations.

4) Directed vs undirected transport

Directionality appears in advection, diode-like circuitry, and biased hopping under fields. In directed mode, only the listed orientation is allowed. The minimum cut can change sharply if alternate return routes vanish.

5) Interpreting cut nodes as bottlenecks

The reported cut set is one minimum solution reconstructed from the residual network. Those vertices form structural bottlenecks: removing any listed node breaks all remaining s–t paths. If multiple minimum cuts exist, another equally small set may also work. Use these nodes to guide redundancy placement and bypass design.

6) Example: lattice-like diffusion network

In a 2D lattice of adsorption sites, adding a single bridge junction can reduce the cut to 1 because all trajectories must pass it. Two parallel corridors typically yield a cut of 2, matching two independent passages.

7) Example: power, optics, and sensing grids

Power meshes, optical junction networks, and sensing topologies benefit from redundancy. A small node cut warns that one hub dominates connectivity. Designers often target cut sizes of at least two for resilience. Parallel junctions and cross-links usually increase cut size and improve single-point tolerance.

8) Reporting results for design decisions

Use s–t mode for a specific injector-to-collector question. Use global connectivity for a conservative robustness metric. Exporting to CSV or PDF helps document the topology, worst pair, and critical nodes for review. Recompute after modifications to verify improvements in connectivity systemwide over time each iteration.

FAQs

1) What is the difference between a node cut and an edge cut?

A node cut removes vertices (junctions), while an edge cut removes links. Node cuts model failures at hubs or sites. Edge cuts model broken connections. This tool focuses on vertex removal between chosen endpoints.

2) Why are the source and target nodes given “infinite” capacity?

The cut is meant to remove intermediate nodes only. Setting very large capacity on the source and target prevents the algorithm from selecting them as part of the minimum cut.

3) What does “cut nodes (one minimum set)” mean?

There can be multiple distinct minimum cuts with the same size. The calculator outputs one valid minimum set reconstructed from the residual network, which is sufficient to explain the vulnerability.

4) How should I interpret a cut size of 0?

A zero value means the target is already unreachable from the source under the chosen directionality. In other words, the graph is disconnected for that ordered pair, so no removals are needed to break connectivity.

5) Can I use weighted or “costly” nodes instead of unit cost?

This version uses unit cost per removable node, matching standard minimum vertex cut size. A weighted version is possible by setting each node’s split-edge capacity to its cost, but it is not enabled here.

6) What does global node connectivity represent?

It is the smallest node cut size over many node pairs, giving a conservative robustness metric. The tool also reports a “worst pair” that achieves that minimum, along with one corresponding cut set.

7) Why are there limits on nodes and edges?

The method runs max-flow computations that grow with graph size. Keeping inputs moderate ensures fast, reliable browser-based interaction. For large networks, consider offline computation or specialized graph libraries.