Bisection width of a graph

Bisection width of a graph — ширина бисекции графа.

The bisection width [math]\displaystyle{ \,bw(G) }[/math] of a graph [math]\displaystyle{ \,G }[/math] is the minimal number of edges between vertex sets [math]\displaystyle{ \,A }[/math] and [math]\displaystyle{ \bar{A} }[/math] of almost equal sizes, i.e. [math]\displaystyle{ A \cup \bar{A} = V(G) }[/math] and [math]\displaystyle{ ||A| - |\bar{A}|| \leq 1 }[/math]. If [math]\displaystyle{ A \subseteq V(G) }[/math], then [math]\displaystyle{ E(A,\bar{A}) }[/math] denotes the set of edges of [math]\displaystyle{ \,G }[/math] having one end in [math]\displaystyle{ \,A }[/math] and another end in [math]\displaystyle{ V(G) \setminus A = \bar{A} }[/math]. The isoperimetric number [math]\displaystyle{ \,i(G) }[/math] of a graph [math]\displaystyle{ \,G }[/math] equals the minimum of the ratio [math]\displaystyle{ |E(A,\bar{A}|/|A| }[/math] for all [math]\displaystyle{ A \subseteq V(G) }[/math] such that [math]\displaystyle{ 2|A| \leq |V(G)| = n }[/math].

From the definitions, we have the following inequality for these characteristics:

[math]\displaystyle{ i(G) \leq \frac{2}{n}bw(G). }[/math]

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.