Maximum Average Degree of a graph

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

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.

Component: graph theory

Author: Nathann Cohen

Reviewer: David Joyner

Merged: sage-4.4.4.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/7529

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:1

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Attachment: trac_7529.patch.gz

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:2

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

[wdjoyner]

comment:3

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:4

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

[7c09a680-e216-4024-bb8e-9bfd4aa7f313]

Reviewer: David Joyner

[7c09a680-e216-4024-bb8e-9bfd4aa7f313]

Description changed:

--- 
+++ 
@@ -2,4 +2,11 @@

 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.

-Nathann
+**Apply:**
+
+1. #8364
+2. #8166
+3. #2203
+4. [trac_7529.patch](https://github.com/sagemath/sage-prod/files/10646929/trac_7529.patch.gz)
+
+Even applying in this order, you might get some fuzz. But that's OK and is not as bad as a hunk failure.

[7c09a680-e216-4024-bb8e-9bfd4aa7f313]

Author: Nathann Cohen

[5e15749f-ac25-4a4f-8d4a-caceb6ae86a4]

comment:6

print pictures

[wdjoyner]

comment:7

Replying to @sagetrac-bascorp2:

print pictures

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

[mwhansen]

Merged: sage-4.4.4.alpha0