# Bisection width of a graph

Перейти к:навигация, поиск

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

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

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

$i(G) \leq \frac{2}{n}bw(G).$

## Литература

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