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 )
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)
Change History (9)
comment:1 Changed 10 years ago by
- Description modified (diff)
- Milestone set to sage-4.3
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
- Report Upstream set to N/A
- Status changed from needs_review to needs_work
comment:3 Changed 10 years ago by
- 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
comment:4 Changed 10 years ago by
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
Changed 10 years ago by
comment:5 Changed 10 years ago by
- Reviewers set to Robert Miller
- Status changed from needs_review to positive_review
comment:6 Changed 10 years ago by
- 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
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.