Bisection width of a graph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Bisection width of a graph''' --- ширина бисекции графа. The '''bisection width''' <math>bw(G)</math> '''of a graph''' <math>G</math> is the …») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 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. | |||
Текущая версия от 16:31, 23 октября 2018
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.