Edge-isoperimetric problem: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Edge-isoperimetric problem''' --- рёберно-изопериметрическая задача. Given a graph <math>G = (V,E,\partial)</math> having the ver…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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 \ | <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>. | ||
Текущая версия от 11:33, 13 апреля 2011
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].