N-Расширяемый граф: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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>\,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>-расширяемым, называется ''[[число расширяемости|числом расширяемости]]'' и обозначается | для которого граф является <math>\,n</math>-расширяемым, называется ''[[число расширяемости|числом расширяемости]]'' и обозначается <math>\,ext(G)</math>. | ||
==Литература== | ==Литература== | ||
[Discrete Math.] | * [Discrete Math.] | ||
Текущая версия от 12:20, 30 августа 2011
[math]\displaystyle{ \,n }[/math]-Расширяемый граф ([math]\displaystyle{ \,n }[/math]-Extendable graph) — Пусть [math]\displaystyle{ \,G }[/math] — конечный, связный, простой [math]\displaystyle{ \,p }[/math]-вершинный граф, [math]\displaystyle{ \,n }[/math] — положительное целое число, удовлетворяющее условию [math]\displaystyle{ 1 \leq n \leq (p/2)-1 }[/math]. [math]\displaystyle{ \,G }[/math] называется [math]\displaystyle{ \,0 }[/math]-расширяемым, если [math]\displaystyle{ \,G }[/math] имеет совершенное паросочетание. [math]\displaystyle{ \,G }[/math] называется [math]\displaystyle{ \,n }[/math]-расширяемым, если [math]\displaystyle{ \,G }[/math] имеет паросочетание размера [math]\displaystyle{ \,n }[/math] и каждое паросочетаниие размера [math]\displaystyle{ \,n }[/math] в [math]\displaystyle{ \,G }[/math] расширяется до совершенного паросочетания. Наибольшее целое [math]\displaystyle{ \,n }[/math], для которого граф является [math]\displaystyle{ \,n }[/math]-расширяемым, называется числом расширяемости и обозначается [math]\displaystyle{ \,ext(G) }[/math].
Литература
- [Discrete Math.]