Аноним

Edge-isoperimetric problem: различия между версиями

Материал из WikiGrapp
нет описания правки
(Новая страница: «'''Edge-isoperimetric problem''' --- рёберно-изопериметрическая задача. Given a graph <math>G = (V,E,\partial)</math> having the ver…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Edge-isoperimetric problem''' --- рёберно-изопериметрическая задача.  
'''Edge-isoperimetric problem''' рёберно-изопериметрическая задача.  


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


<math>\Theta(S) = \{e \in E: \, \partial(e) = \{v,w\}, v \in S \& w \not \in S\}.</math>
<math>\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
Then, the '''edge-isoperimetric problem''' is to
minimize <math>|\Theta(S)|</math> over all <math>S \subseteq V</math> such that <math>|S| = k</math>  
minimize <math>|\Theta(S)|</math> over all <math>S \subseteq V</math> such that <math>|S| = k</math>  
for a given <math>k \in Z^{+}</math>.
for a given <math>k \in Z^{+}</math>.