Аноним

N-Расширяемый граф: различия между версиями

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''<math>n</math>-Расширяемый граф''' (''[[n-Extendable graph|<math>n</math>-Extendable graph]]'') -
'''<math>\,n</math>-Расширяемый граф''' (''[[n-Extendable graph|<math>\,n</math>-Extendable graph]]'')
Пусть <math>G</math> --- [[конечный граф|конечный]], [[связный граф|связный]], [[простой граф|простой]] <math>p</math>-вершинный [[граф]], <math>n</math> ---
Пусть <math>\,G</math> [[конечный граф|конечный]], [[связный граф|связный]], [[простой граф|простой]] <math>\,p</math>-вершинный [[граф]], <math>\,n</math>
положительное целое число, удовлетворяющее условию <math>1 \leq n \leq
положительное целое число, удовлетворяющее условию <math>1 \leq n \leq
(p/2)-1</math>. <math>G</math> называется <math>0</math>-расширяемым, если <math>G</math> имеет [[совершенное паросочетание]]. <math>G</math> называется <math>n</math>-расширяемым, если
(p/2)-1</math>. <math>\,G</math> называется <math>\,0</math>-расширяемым, если <math>\,G</math> имеет [[совершенное паросочетание]]. <math>\,G</math> называется <math>\,n</math>-расширяемым, если
<math>G</math> имеет [[паросочетание]] размера <math>n</math> и каждое паросочетаниие размера <math>n</math> в
<math>\,G</math> имеет [[паросочетание]] размера <math>\,n</math> и каждое паросочетаниие размера <math>\,n</math> в
<math>G</math> расширяется до совершенного паросочетания. Наибольшее целое <math>n</math>,
<math>\,G</math> расширяется до совершенного паросочетания. Наибольшее целое <math>\,n</math>,
для которого граф является <math>n</math>-расширяемым, называется ''[[число расширяемости|числом расширяемости]]'' и обозначается ext<math>(G)</math>.
для которого граф является <math>\,n</math>-расширяемым, называется ''[[число расширяемости|числом расширяемости]]'' и обозначается <math>\,ext(G)</math>.
==Литература==
==Литература==
[Discrete Math.]
* [Discrete Math.]