Opened 10 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 mvngu)

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:

  1. #8364
  2. #8166
  3. #2203
  4. trac_7529.patch

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)

trac_7529.patch (6.4 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (9)

comment:1 Changed 9 years ago by ncohen

  • Status changed from new to needs_review

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

Changed 9 years ago by ncohen

comment:2 Changed 9 years ago by ncohen

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 wdj

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

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 mvngu

  • Authors set to Nathann Cohen
  • Description modified (diff)
  • Reviewers set to David Joyner

comment:6 follow-up: Changed 9 years ago by bascorp2

comment:7 in reply to: ↑ 6 Changed 9 years ago by wdj

Replying to bascorp2:

print pictures

This looks like spam but I didn't try the link.

comment:8 Changed 9 years ago by mhansen

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