Fractional k-factor

Материал из WikiGrapp
Версия от 14:53, 3 мая 2011; Glk (обсуждение | вклад) (Новая страница: «'''Fractional <math>k</math>-factor''' ---дробный <math>k</math>-фактор. Let <math>g</math> and <math>f</math> be two integer-valued functions defined…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Fractional [math]\displaystyle{ k }[/math]-factor ---дробный [math]\displaystyle{ k }[/math]-фактор.

Let [math]\displaystyle{ g }[/math] and [math]\displaystyle{ f }[/math] be two integer-valued functions defined on [math]\displaystyle{ V(G) }[/math]. Let [math]\displaystyle{ h: \; E(G) \rightarrow [0,1] }[/math] be a function. A function [math]\displaystyle{ h }[/math] is called a fractional [math]\displaystyle{ (g,f) }[/math]-factor if [math]\displaystyle{ g(x) \leq h(E_{x}) \leq f(x) }[/math] holds for any vertex [math]\displaystyle{ x \in V(G) }[/math], where [math]\displaystyle{ h(E_{x}) = \sum_{e \in E_{x}}h(e) }[/math] and [math]\displaystyle{ E_{x} = \{e \in E(G)| e }[/math] is incident with [math]\displaystyle{ x }[/math] in [math]\displaystyle{ E(G)\} }[/math]. A fractional [math]\displaystyle{ (g,f) }[/math]-factor is called a fractional [math]\displaystyle{ [a,b] }[/math]-factor if [math]\displaystyle{ g(x) \equiv a }[/math] and [math]\displaystyle{ f(x) \equiv b }[/math], where [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] are two integers such that [math]\displaystyle{ a \leq b }[/math]. A fractional [math]\displaystyle{ [a,b] }[/math]-factor is called a fractional [math]\displaystyle{ k }[/math]-factor if [math]\displaystyle{ a = b = k }[/math]. In particular, a fractional [math]\displaystyle{ [0,1] }[/math]-factor is also called a fractional matching and fractional 1-factor is also called a fractional perfect matching.