Namespaces
Variants
Actions

Difference between revisions of "Factorization"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
 +
{{TEX|done}}
 
''in graph theory''
 
''in graph theory''
  
The decomposition of a [[Graph|graph]] into edge-disjoint spanning subgraphs of a special form. In the general case a factor is a spanning subgraph with a given property. An example of such a property is regularity. A regular spanning subgraph of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f0381001.png" /> is called a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f0381003.png" />-factor; a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f0381004.png" />-factor is also called a perfect matching. A graph is called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f0381006.png" />-factorizable (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f0381008.png" />-factorable) if it can be represented as a union of edge-disjoint <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f0381009.png" />-factors.
+
The decomposition of a [[Graph|graph]] into edge-disjoint spanning subgraphs of a special form. In the general case a factor is a spanning subgraph with a given property. An example of such a property is regularity. A regular spanning subgraph of degree $k$ is called a $k$-factor; a $1$-factor is also called a perfect matching. A graph is called $k$-factorizable (or $k$-factorable) if it can be represented as a union of edge-disjoint $k$-factors.
  
In graph theory one considers questions on the existence of factors of one type or another in an arbitrary graph, on the number of factors, and on the possibility of a factorization of a given type for different classes of graphs. It is known, for example, that a complete graph with an even number of vertices and a complete bipartite graph (cf. [[Graph, bipartite|Graph, bipartite]]) with the same number of vertices in each part are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810010.png" />-factorizable. A connected graph is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810011.png" />-factorizable if and only if it is a regular graph of even degree. A graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810012.png" /> has a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810013.png" />-factor if and only if it has an even number of vertices and if there is no subset of vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810014.png" /> such that the number of components with an odd number of vertices of the graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810015.png" />, obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810016.png" /> by deleting the vertices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810017.png" />, exceeds <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810018.png" />. Every two-connected regular graph of degree 3 can be decomposed into a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810019.png" />-factor and a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810020.png" />-factor which are edge-disjoint.
+
In graph theory one considers questions on the existence of factors of one type or another in an arbitrary graph, on the number of factors, and on the possibility of a factorization of a given type for different classes of graphs. It is known, for example, that a complete graph with an even number of vertices and a complete bipartite graph (cf. [[Graph, bipartite|Graph, bipartite]]) with the same number of vertices in each part are $1$-factorizable. A connected graph is $2$-factorizable if and only if it is a regular graph of even degree. A graph $G$ has a $1$-factor if and only if it has an even number of vertices and if there is no subset of vertices $U$ such that the number of components with an odd number of vertices of the graph $G\setminus U$, obtained from $G$ by deleting the vertices of $U$, exceeds $|U|$. Every two-connected regular graph of degree 3 can be decomposed into a $1$-factor and a $2$-factor which are edge-disjoint.
  
Examples of non-regular factors are spanning trees (cf. [[Tree|Tree]]) and forests, spanning planar subgraphs (see [[Graph imbedding|Graph imbedding]]), etc. Connected with the decomposition of a graph into spanning forests is the numerical characteristic called the arboricity; this is the least number of edge-disjoint spanning forests whose union is the graph. The arboricity of an arbitrary graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810021.png" /> is equal to
+
Examples of non-regular factors are spanning trees (cf. [[Tree|Tree]]) and forests, spanning planar subgraphs (see [[Graph imbedding|Graph imbedding]]), etc. Connected with the decomposition of a graph into spanning forests is the numerical characteristic called the arboricity; this is the least number of edge-disjoint spanning forests whose union is the graph. The arboricity of an arbitrary graph $G$ is equal to
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810022.png" /></td> </tr></table>
+
$$\max_k=\{\frac{g_k}{k-1}\},$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810023.png" /> is the largest number of edges in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810024.png" />-vertex subgraphs of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810025.png" />.
+
where $g_k$ is the largest number of edges in the $k$-vertex subgraphs of $G$.
  
 
====References====
 
====References====
Line 17: Line 18:
  
 
====Comments====
 
====Comments====
A spanning subgraph of a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810026.png" /> is a subgraph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810027.png" /> whose set of vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810028.png" /> is equal to the set of vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810029.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810030.png" />.
+
A spanning subgraph of a graph $G=(V,E)$ is a subgraph $G_1=(V_1,E_1)$ whose set of vertices $V_1$ is equal to the set of vertices $V$ of $G$.
  
The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810032.png" />-factor theorem quoted above is due to W.T. Tutte. Given a vertex function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810033.png" />, a factor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810034.png" /> is called an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810036.png" />-factor if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810037.png" /> for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810038.png" />, the vertex set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810039.png" />. Tutte also proved an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810041.png" />-factor theorem. The results on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f038/f038100/f03810043.png" />-factors mentioned above are due to J. Petersen [[#References|[a1]]]. A comprehensive treatment of all these results is given by Tutte in [[#References|[a2]]]. A recent survey is [[#References|[a3]]].
+
The $1$-factor theorem quoted above is due to W.T. Tutte. Given a vertex function $f$, a factor $F$ is called an $f$-factor if $d(v|F)=f(x)$ for every $v\in V$, the vertex set of $G$. Tutte also proved an $f$-factor theorem. The results on $2$-factors mentioned above are due to J. Petersen [[#References|[a1]]]. A comprehensive treatment of all these results is given by Tutte in [[#References|[a2]]]. A recent survey is [[#References|[a3]]].
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Petersen,  "Die theorie der regulären Graphen"  ''Acta. Math.'' , '''15'''  (1891)  pp. 193–220</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  W.T. Tutte,  "Graph factors"  ''Combinatorica'' , '''1'''  (1981)  pp. 79–97</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J. Akiyama,  M. Kano,  "Factors and factorizations of graphs - a survey"  ''J. Graph Theory'' , '''9'''  (1985)  pp. 1–42</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Petersen,  "Die theorie der regulären Graphen"  ''Acta. Math.'' , '''15'''  (1891)  pp. 193–220</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  W.T. Tutte,  "Graph factors"  ''Combinatorica'' , '''1'''  (1981)  pp. 79–97</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J. Akiyama,  M. Kano,  "Factors and factorizations of graphs - a survey"  ''J. Graph Theory'' , '''9'''  (1985)  pp. 1–42</TD></TR></table>

Revision as of 14:40, 17 July 2014

in graph theory

The decomposition of a graph into edge-disjoint spanning subgraphs of a special form. In the general case a factor is a spanning subgraph with a given property. An example of such a property is regularity. A regular spanning subgraph of degree $k$ is called a $k$-factor; a $1$-factor is also called a perfect matching. A graph is called $k$-factorizable (or $k$-factorable) if it can be represented as a union of edge-disjoint $k$-factors.

In graph theory one considers questions on the existence of factors of one type or another in an arbitrary graph, on the number of factors, and on the possibility of a factorization of a given type for different classes of graphs. It is known, for example, that a complete graph with an even number of vertices and a complete bipartite graph (cf. Graph, bipartite) with the same number of vertices in each part are $1$-factorizable. A connected graph is $2$-factorizable if and only if it is a regular graph of even degree. A graph $G$ has a $1$-factor if and only if it has an even number of vertices and if there is no subset of vertices $U$ such that the number of components with an odd number of vertices of the graph $G\setminus U$, obtained from $G$ by deleting the vertices of $U$, exceeds $|U|$. Every two-connected regular graph of degree 3 can be decomposed into a $1$-factor and a $2$-factor which are edge-disjoint.

Examples of non-regular factors are spanning trees (cf. Tree) and forests, spanning planar subgraphs (see Graph imbedding), etc. Connected with the decomposition of a graph into spanning forests is the numerical characteristic called the arboricity; this is the least number of edge-disjoint spanning forests whose union is the graph. The arboricity of an arbitrary graph $G$ is equal to

$$\max_k=\{\frac{g_k}{k-1}\},$$

where $g_k$ is the largest number of edges in the $k$-vertex subgraphs of $G$.

References

[1] F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9


Comments

A spanning subgraph of a graph $G=(V,E)$ is a subgraph $G_1=(V_1,E_1)$ whose set of vertices $V_1$ is equal to the set of vertices $V$ of $G$.

The $1$-factor theorem quoted above is due to W.T. Tutte. Given a vertex function $f$, a factor $F$ is called an $f$-factor if $d(v|F)=f(x)$ for every $v\in V$, the vertex set of $G$. Tutte also proved an $f$-factor theorem. The results on $2$-factors mentioned above are due to J. Petersen [a1]. A comprehensive treatment of all these results is given by Tutte in [a2]. A recent survey is [a3].

References

[a1] J. Petersen, "Die theorie der regulären Graphen" Acta. Math. , 15 (1891) pp. 193–220
[a2] W.T. Tutte, "Graph factors" Combinatorica , 1 (1981) pp. 79–97
[a3] J. Akiyama, M. Kano, "Factors and factorizations of graphs - a survey" J. Graph Theory , 9 (1985) pp. 1–42
How to Cite This Entry:
Factorization. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Factorization&oldid=32464
This article was adapted from an original article by A.A. Sapozhenko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article