Graph factorization: Difference between revisions

Revision as of 20:58, 29 January 2014

Revision as of 20:27, 23 April 2014

Line 1:

{{Distinguish|Factor graph}}

{{Cleanup|date=January 2010}}

[[Image:Desargues graph 3color edge.svg|thumb|200px|1-factorization of [[Desargues graph]]: each color class is a 1-factor.]]

Line 17 ⟶ 15:

===Complete graphs===

[[File:Complete-edge-coloring.svg|thumb|200px|An easy to generate 1-factorization of ''K''₈. Eachin setwhich each 1-factor consists of edgesan withedge from the samecenter colorto isa vertex of a 1-factor.[[heptagon]] together with all possible perpendicular edges]]

A 1-factorization of a [[complete graph]] corresponds to pairings in a [[round-robin tournament]]. The 1-factorization of complete graphs is a special case of [[Baranyai's theorem]] concerning the 1-factorization of complete [[hypergraph]]s.

Draw seven vertices distributed evenly around a circle, and one in the middle, for a total of eight vertices. Join the middle point to any single point on the circle; call this line ''L''. Join points to other points on the circle together [[if and only if]] they can be joined together with a line [[Orthogonality|orthogonal]] to ''L''. Since the points were arranged evenly, this will produce a matching (in fact a perfect matching) of these eight vertices.

One method for constructing a 1-factorization of a complete graph involves placing all but one of the vertices on a circle, forming a [[regular polygon]], with the remaining vertex at the center of the circle. With this arrangement of vertices, one way of constructing a 1-factor of the graph is to choose an edge ''e'' from the center to a single polygon vertex together with all possible edges that lie on lines perpendicular to ''e''. The 1-factors that can be constructed in this way form a 1-factorization of the graph.

Now rotate the lines one vertex to the right: Start over again with the eight vertices as described and join the center point to the point in the circle directly clockwise from the first one chosen. Join the other points on the circle in a similar manner as before. This is again another perfect matching of these eight points.

Each of these perfect matchings can also be looked at as a 1-factor of the [[complete graph]] on eight vertices, ''K''₈. Continuing the process above, you will form a 1-factorization of ''K''₈. This is a proof that there exists a 1-factorization of ''K''_2''n'' for all ''n''.

A 1-factorization of a [[complete graph]] corresponds to pairings in a [[round-robin tournament]]. The 1-factorization of complete graphs is a special case of [[Baranyai's theorem]] concerning the 1-factorization of complete [[hypergraph]]s.

===1-factorization conjecture===