Opened 10 years ago

Closed 10 years ago

#7365 closed enhancement (fixed)

Petersen's 2-factor theorem

Reported by: ncohen Owned by: rlm
Priority: major Milestone: sage-4.3
Component: graph theory Keywords:
Cc: Merged in: sage-4.3.rc1
Authors: Nathann Cohen Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

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

Attachments (3)

trac_7365.patch (3.2 KB) - added by ncohen 10 years ago.
tmp_4.png (133.6 KB) - added by rlm 10 years ago.
trac_7365-doctest.patch (920 bytes) - added by rlm 10 years ago.

Download all attachments as: .zip

Change History (9)

comment:1 Changed 10 years ago by ncohen

  • Description modified (diff)
  • Milestone set to sage-4.3
  • Status changed from new to needs_review

comment:2 Changed 10 years ago by rlm

  • Report Upstream set to N/A
  • Status changed from needs_review to needs_work

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.

comment:3 Changed 10 years ago by ncohen

  • Description modified (diff)
  • Status changed from needs_work to needs_review

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

Changed 10 years ago by ncohen

comment:4 Changed 10 years ago by ncohen

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

Changed 10 years ago by rlm

Changed 10 years ago by rlm

comment:5 Changed 10 years ago by rlm

  • Authors set to Nathann Cohen
  • Reviewers set to Robert Miller
  • Status changed from needs_review to positive_review

comment:6 Changed 10 years ago by mhansen

  • Merged in set to sage-4.3.rc1
  • Milestone changed from sage-4.3.1 to sage-4.3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.