N-Расширяемый граф

Материал из WEGA
Версия от 15:15, 14 января 2010; Glk (обсуждение | вклад) (Создана новая страница размером '''<math>n</math>-Расширяемый граф''' (''<math>n</math>-Extendable graph'') - Пусть <math>G</math> --- конечны...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

[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.]