Bisection width of a graph

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

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.