4625
правок
N-Расширяемый граф: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''<math>n</math>-Расширяемый граф''' (''<math>n</math>-Extendable graph'') - Пусть <math>G</math> --- конечны...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>n</math>-Расширяемый граф''' (''<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> имеет совершенное | (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>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>-расширяемым, называется ''[[число расширяемости|числом расширяемости]]'' и обозначается ext<math>(G)</math>. | ||
==Литература== | ==Литература== | ||
[Discrete Math.] | [Discrete Math.] | ||