# Changes between Initial Version and Version 1 of Ticket #7365

Ignore:
Timestamp:
11/18/09 18:09:22 (11 years ago)
Comment:

### Legend:

Unmodified
• Property Status changed from new to needs_review
• Property Milestone changed from to sage-4.3
 initial 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