Аноним

Bisection width of a graph: различия между версиями

Материал из WikiGrapp
нет описания правки
(Новая страница: «'''Bisection width of a graph''' --- ширина бисекции графа. The '''bisection width''' <math>bw(G)</math> '''of a graph''' <math>G</math> is the …»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Bisection width of a graph''' --- ширина бисекции графа.  
'''Bisection width of a graph''' — ''[[ширина бисекции графа]].''


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


<math>i(G) \leq \frac{2}{n}bw(G).</math>
:::::<math>i(G) \leq \frac{2}{n}bw(G).</math>
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.