Bicritical graph: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Bicritical graph''' --- бикритический граф. A finite, undirected, connected and simple graph <math>G</math> is said to be '''bicritical''' if <m…») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Bicritical graph''' | '''Bicritical graph''' — ''[[бикритический граф]].'' | ||
A finite, undirected, connected and simple graph <math>G</math> is said to be | |||
'''bicritical''' if <math>G - u - v</math> has a ''perfect matching'' for each | A [[finite graph|finite]], [[undirected graph|undirected]], [[connected graph|connected]] and [[simple graph]] <math>\,G</math> is said to be | ||
pair of vertices <math>u</math> and <math>v</math> in <math>G</math> such that <math>u \neq v</math>. | '''bicritical''' if <math>\,G - u - v</math> has a ''[[perfect matching]]'' for each | ||
pair of [[vertex|vertices]] <math>u</math> and <math>v</math> in <math>\,G</math> such that <math>u \neq v</math>. | |||
Bicritical graphs play a central role in the decomposition theory of | Bicritical graphs play a central role in the decomposition theory of | ||
graphs in terms of their maximum ''matchings''. | graphs in terms of their maximum ''matchings''. | ||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 16:31, 23 октября 2018
Bicritical graph — бикритический граф.
A finite, undirected, connected and simple graph [math]\displaystyle{ \,G }[/math] is said to be bicritical if [math]\displaystyle{ \,G - u - v }[/math] has a perfect matching for each pair of vertices [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] in [math]\displaystyle{ \,G }[/math] such that [math]\displaystyle{ u \neq v }[/math].
Bicritical graphs play a central role in the decomposition theory of graphs in terms of their maximum matchings.
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.