Berge's Formula: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Berge's Formula''' --- формула Бержа. Let <math>G</math> be a graph and let <math>o(G)</math> be the number of ''odd components'' of <math>G</math>.…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Berge's Formula''' | '''Berge's Formula''' — ''[[формула Бержа]].'' | ||
Let <math>G</math> be a graph and let <math>o(G)</math> be the number of ''odd components'' of <math>G</math>. | Let <math>\,G</math> be a [[graph, undirected graph, nonoriented graph|graph]] and let <math>\,o(G)</math> be the number of ''odd components'' of <math>\,G</math>. | ||
'''Berge's Formula''' for estimating the ''deficiency'' of the graph: | '''Berge's Formula''' for estimating the ''deficiency'' of the graph: | ||
<math>def(G) = \max_{S \subset V(G)} \{o(G \setminus S) - |S|\}.</math> | <math>def(G) = \max_{S \subset V(G)} \{o(G \setminus S) - |S|\}.</math> | ||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 13:30, 12 января 2012
Berge's Formula — формула Бержа.
Let [math]\displaystyle{ \,G }[/math] be a graph and let [math]\displaystyle{ \,o(G) }[/math] be the number of odd components of [math]\displaystyle{ \,G }[/math].
Berge's Formula for estimating the deficiency of the graph:
[math]\displaystyle{ def(G) = \max_{S \subset V(G)} \{o(G \setminus S) - |S|\}. }[/math]
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.