K-Factor of a graph: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Новая страница: «'''<math>k</math>-Factor of a graph''' --- <math>k</math>-фактор графа. A spanning subgraph <math>H</math> of a graph <math>G</math> is a '''<math>k</ma…»)
 
(нет различий)

Текущая версия от 14:27, 27 апреля 2011

[math]\displaystyle{ k }[/math]-Factor of a graph --- [math]\displaystyle{ k }[/math]-фактор графа.

A spanning subgraph [math]\displaystyle{ H }[/math] of a graph [math]\displaystyle{ G }[/math] is a [math]\displaystyle{ k }[/math]-factor if all vertices of [math]\displaystyle{ H }[/math] have degree [math]\displaystyle{ k }[/math]. A graph [math]\displaystyle{ G }[/math] is [math]\displaystyle{ k }[/math]-factorable (factorizable) if its edges can be partitioned into [math]\displaystyle{ k }[/math]-factors. A classical result of Petersen (1891) states that any [math]\displaystyle{ 2k }[/math]-regular graph is 2-factorable.

Let [math]\displaystyle{ g }[/math] and [math]\displaystyle{ f }[/math] be integer-valued functions defined on [math]\displaystyle{ V(G) }[/math] such that [math]\displaystyle{ 0 \leq g(x) \leq f(x) }[/math] for every [math]\displaystyle{ x \in V(G) }[/math]. A [math]\displaystyle{ (g,f) }[/math]-factor of [math]\displaystyle{ G }[/math] is a spanning subgraph [math]\displaystyle{ F }[/math] of [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ g(x) \leq d_{F}(x) \leq f(x) }[/math] for every [math]\displaystyle{ x \in V(G) }[/math]. If [math]\displaystyle{ G }[/math] itself is a [math]\displaystyle{ (g,f) }[/math]-factor, then [math]\displaystyle{ G }[/math] is called a [math]\displaystyle{ (g,f) }[/math]-graph. A [math]\displaystyle{ (g,f) }[/math]-factorization [math]\displaystyle{ {\mathcal F} = \{F_{1}, \ldots, F_{m}\} }[/math] of [math]\displaystyle{ G }[/math] is a partition of [math]\displaystyle{ G }[/math] into edge-disjoint [math]\displaystyle{ (g,f) }[/math]-factors [math]\displaystyle{ F_{1}, \ldots, F_{m} }[/math]. Let [math]\displaystyle{ H }[/math] be a subgraph of [math]\displaystyle{ G }[/math] with [math]\displaystyle{ m }[/math] edges, then [math]\displaystyle{ {\mathcal F} }[/math] is called orthogonal to [math]\displaystyle{ H }[/math] if each [math]\displaystyle{ F_{i} }[/math] has exactly one edge in common with [math]\displaystyle{ H }[/math].