Changes between Initial Version and Version 1 of Ticket #7365


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

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #7365

    • Property Status changed from new to needs_review
    • Property Milestone changed from to sage-4.3
  • Ticket #7365 – Description

    initial v1  
    1 Implement a function corresponding to Petersen's theorem on 2-factors.
     1As the docstring says :
    22
    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.
     3Petersen's 2-factor decomposition theorem asserts that any
     4`2r`-regular graph `G` can be decomposed into 2-factors.
     5Equivalently, it means that the edges of any `2r`-regular
     6graphs can be partitionned in `r` sets `C_1,\dots,C_r` such
     7that for all `i`, the set `C_i` is a disjoint union of cycles
     8( a 2-regular graph ).
    49
     10As any graph of maximal degree `\Delta` can be completed into
     11a regular graph of degree `2\lceil\frac\Delta 2\rceil`, this
     12result also means that the edges of any graph of degree `\Delta`
     13can 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
     15graph of maximal degree 2 ( a disjoint union of paths
     16and cycles ).
     17
     18
     19This 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
     21As 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
     27Perhaps the best thing to do is to review these patches before this very one.
     28
     29Nathann