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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''<math>n</math>-Расширяемый граф''' (''<math>n</math>-Extendable graph'') - Пусть <math>G</math> --- конечны...)
 
Нет описания правки
Строка 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.]

Версия от 16:41, 15 января 2010

[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]-расширяемым, называется числом расширяемости и обозначается ext[math]\displaystyle{ (G) }[/math].

Литература

[Discrete Math.]