Petersen's 2-factor theorem

[nathanncohen]

As the docstring says :

Petersen's 2-factor decomposition theorem asserts that any
2r-regular graph G can be decomposed into 2-factors.
Equivalently, it means that the edges of any 2r-regular
graphs can be partitionned in r sets C_1,\dots,C_r such
that for all i, the set C_i is a disjoint union of cycles
( a 2-regular graph ).

As any graph of maximal degree \Delta can be completed into
a regular graph of degree 2\lceil\frac\Delta 2\rceil, this
result also means that the edges of any graph of degree \Delta
can be partitionned in r=2\lceil\frac\Delta 2\rceil sets
C_1,\dots,C_r such that for all i, the set C_i is a
graph of maximal degree 2 ( a disjoint union of paths
and cycles ).

Nathann

Component: graph theory

Author: Nathann Cohen

Reviewer: Robert Miller

Merged: sage-4.3.rc1

Issue created by migration from https://trac.sagemath.org/ticket/7365

[nathanncohen]

Description changed:

--- 
+++ 
@@ -1,5 +1,29 @@
-Implement a function corresponding to Petersen's theorem on 2-factors.
+As the docstring says :
 
-This theorem says that any 2r-regular graphs can be decomposed in 2-factors. If the graph is not regular and is of maximum degree Delta, then it can be decomposed as an union of Delta/2 disjoints (<=2)-factors.
+Petersen's 2-factor decomposition theorem asserts that any
+`2r`-regular graph `G` can be decomposed into 2-factors.
+Equivalently, it means that the edges of any `2r`-regular
+graphs can be partitionned in `r` sets `C_1,\dots,C_r` such
+that for all `i`, the set `C_i` is a disjoint union of cycles
+( a 2-regular graph ).
+
+As any graph of maximal degree `\Delta` can be completed into
+a regular graph of degree `2\lceil\frac\Delta 2\rceil`, this
+result also means that the edges of any graph of degree `\Delta`
+can be partitionned in `r=2\lceil\frac\Delta 2\rceil` sets
+`C_1,\dots,C_r` such that for all `i`, the set `C_i` is a
+graph of maximal degree 2 ( a disjoint union of paths
+and cycles ).
 
 
+This patch both creates a new file in the graph directory, named graph_decomposition ( which will very soon contain many functions,  do not worry about it !! ) into which is defined the function two_factor_petersen.
+
+As the moment, this patch requires many others which have not been merged :
+* #6679 Edge coloring function
+* #7270 Linear Programming class
+* #7268 or #7333 as a LP solver
+* #7364 eulerian orientation of a graph
+
+Perhaps the best thing to do is to review these patches before this very one.
+
+Nathann

[rlmill]

comment:2

If you're introducing a new module in sage.graphs, the header of the file should be much more descriptive of what the module is for, etc... Take a look at some of the other files for examples.

I'm (personally) very curious about what else you plan on including in graph_decompositions...

The patch applies cleanly, and the code looks good. Once again, I'd like to see a little more examples in the documentation.

[nathanncohen]

Description changed:

--- 
+++ 
@@ -15,15 +15,4 @@
 graph of maximal degree 2 ( a disjoint union of paths
 and cycles ).
 
-
-This patch both creates a new file in the graph directory, named graph_decomposition ( which will very soon contain many functions,  do not worry about it !! ) into which is defined the function two_factor_petersen.
-
-As the moment, this patch requires many others which have not been merged :
-* #6679 Edge coloring function
-* #7270 Linear Programming class
-* #7268 or #7333 as a LP solver
-* #7364 eulerian orientation of a graph
-
-Perhaps the best thing to do is to review these patches before this very one.
-
 Nathann

[nathanncohen]

comment:3

Hello !!!

As mentionned, I moved this function toward graph.py, and will patiently wait for the splitting of graph.py to begin creating new files.. :-)

(please do not forget to install GLPK or CBC before testing it because of #7734)

Nathann

[nathanncohen]

comment:4

Attachment: trac_7365.patch.gz

I tried to find another example, but could not find any interesting/funny one (the theorem and its proof by themselves are enough to make me laugh :-) ). If you can think of a good one, just tell me and I'll add it :-)

Nathann