| 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 |
