Edge-isoperimetric problem

Edge-isoperimetric problem — рёберно-изопериметрическая задача.

Given a graph [math]\displaystyle{ G = (V,E,\partial) }[/math] having the vertex-set [math]\displaystyle{ V }[/math], edge-set [math]\displaystyle{ E }[/math] and boundary-function [math]\displaystyle{ \partial: \, E \rightarrow \left(\begin{array}{c} V \\ 2 \end{array}\right) }[/math] which identifies the pair of vertices incident to each edge, we define

[math]\displaystyle{ \Theta(S) = \{e \in E: \, \partial(e) = \{v,w\}, v \in S \And w \not \in S\}. }[/math]

Then, the edge-isoperimetric problem is to minimize [math]\displaystyle{ |\Theta(S)| }[/math] over all [math]\displaystyle{ S \subseteq V }[/math] such that [math]\displaystyle{ |S| = k }[/math] for a given [math]\displaystyle{ k \in Z^{+} }[/math].