Bicritical graph: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Bicritical graph''' --- бикритический граф. A finite, undirected, connected and simple graph <math>G</math> is said to be '''bicritical''' if <m…»)
 
Нет описания правки
 
Строка 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.