Graph factorization

Is a factor in the graph theory a subgraph of a graph are provided at the level of the nodes as well as the relationship of the graph in which certain requirements. Factors play an important role in the theory of the matching problem and the Hamiltonian cycle problem.

Definition

Be a simple graph and a mapping which assigns to each node of the graph is a natural number. A g- factor is then a subgraph of nodes with the same amount as, in which each node has the degree, so it has exactly neighbors.

Applies to all nodes with the condition, so have all the nodes of the subgraph exactly neighbors, we speak accordingly of an a- factor. Other hand, applies to all nodes the condition, so have all the nodes of the subgraphs at least and at most neighbors, we speak accordingly of an [a, b] - factor.

Equivalent definition

Equivalent to the above definition is the following: a regular part of a- graph subtends the graph is called a factor.

Related terms

A decomposition of a graph in a- factors is called a factorization. A non-empty graph is called factor - critical if a 1- factorization is possible by the removal of any node.

Examples

A pairing is a factor, that is a subgraph of, in which each node has at most one neighbor. A perfect pairing is, however, a 1- factor, ie, a subgraph of, in which each node has exactly one neighbor. Hamiltonian graphs finally have 2- factors, where each node has exactly two neighbors.

Existence of factors

The 1 -factor theorem of Tutte states that one can and construct a graph if and only has a 1-factor, if a factor has. This is the definition of a reduction in the sense of theoretical computer science. Conversely, since 1- factors are special cases of factors, the factor problem is equivalent to the 1- factor problem.