3 | | 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. |
| 3 | Petersen's 2-factor decomposition theorem asserts that any |
| 4 | `2r`-regular graph `G` can be decomposed into 2-factors. |
| 5 | Equivalently, it means that the edges of any `2r`-regular |
| 6 | graphs can be partitionned in `r` sets `C_1,\dots,C_r` such |
| 7 | that for all `i`, the set `C_i` is a disjoint union of cycles |
| 8 | ( a 2-regular graph ). |
| 10 | As any graph of maximal degree `\Delta` can be completed into |
| 11 | a regular graph of degree `2\lceil\frac\Delta 2\rceil`, this |
| 12 | result also means that the edges of any graph of degree `\Delta` |
| 13 | can be partitionned in `r=2\lceil\frac\Delta 2\rceil` sets |
| 14 | `C_1,\dots,C_r` such that for all `i`, the set `C_i` is a |
| 15 | graph of maximal degree 2 ( a disjoint union of paths |
| 16 | and cycles ). |
| 17 | |
| 18 | |
| 19 | 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. |
| 20 | |
| 21 | As the moment, this patch requires many others which have not been merged : |
| 22 | * #6679 Edge coloring function |
| 23 | * #7270 Linear Programming class |
| 24 | * #7268 or #7333 as a LP solver |
| 25 | * #7364 eulerian orientation of a graph |
| 26 | |
| 27 | Perhaps the best thing to do is to review these patches before this very one. |
| 28 | |
| 29 | Nathann |