Opened 9 years ago
Closed 9 years ago
#7529 closed enhancement (fixed)
Maximum Average Degree of a graph
Reported by: | ncohen | Owned by: | rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.4.4 |
Component: | graph theory | Keywords: | |
Cc: | Merged in: | sage-4.4.4.alpha0 | |
Authors: | Nathann Cohen | Reviewers: | David Joyner |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
The maximum average degree of a graph is the maximum, over all subgraphs H of a graph G, of average_degree(H).
This can be computed in polynomial time ( though I do not know of any practical way to do it ) and could be used, for example, as a certificate for negative answers in #7528.
Apply:
Even applying in this order, you might get some fuzz. But that's OK and is not as bad as a hunk failure.
Attachments (1)
Change History (9)
comment:1 Changed 9 years ago by
- Status changed from new to needs_review
Changed 9 years ago by
comment:2 Changed 9 years ago by
For an explanation of the Linear Program used to solve this problem, see the LP chapter from : http://code.google.com/p/graph-theory-algorithms-book/
Nathann
comment:3 Changed 9 years ago by
- Status changed from needs_review to positive_review
This installs fine on 4.4.2.a0, passes sage -testall both before and after installing glpk (except for unrelated failures).
Also, the docs look good and I tested it on other examples and it works as claimed:
sage: g = graphs.RandomGNP(20,.3) sage: h = graphs.RandomGNP(20,.2) sage: j = g+h sage: j.density() 49/390 sage: h.density() 3/19 sage: g.density() 34/95 sage: RR(g.density()) 0.357894736842105 sage: RR(h.density()) 0.157894736842105 sage: j.maximum_average_degree() 34/5 sage: h.average_degree() 3 sage: g.average_degree() 34/5
comment:4 Changed 9 years ago by
Thaaaaaaank you so much !!! The other LP tickets are just applications of the following thing : if a graph has maximum average degree strictly less than 2 ( so 2-epsilon in the code, or 1-epsilon as it is sometimes divided) then it is acyclic -> a forest !!
So this ticket really is they key to all others ! When I found how to solve this one I knew how to write the others, so there shouldn't be any surprise in them :-)
Thank you again !!
Nathann
comment:5 Changed 9 years ago by
- Description modified (diff)
- Reviewers set to David Joyner
comment:6 follow-up: ↓ 7 Changed 9 years ago by
comment:7 in reply to: ↑ 6 Changed 9 years ago by
comment:8 Changed 9 years ago by
- Merged in set to sage-4.4.4.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
After some thinking, is was easy to write it through Linear Programming :-)
I also wrote a pretty elementary average_degree function, that I had been missing for some time !
Nathann