Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #1111

Re: Help with graph theory puzzle solution analysis

Cross-posted to 4 groups.

Show key headers only | View raw

On Sat, 17 Dec 2011, Andrew Tomazos wrote:

> I was involved in a programming competition recently and one of the
> questions was approximately the following...
>
> Let S(N) be the set of all graphs with N vertices and N-1 edges with
> the following properties:
> - undirected
> - connected
> - no loop edges (no edge has both ends on same vertex)
> - no double edges (any pair of vertices have at most one edge
> directly connecting them)
>
> The number of edge ends joined to a vertex is called the vertex's
> degree.
>
> We are given an array of scores[] for each possible vertex degree.
> (ie scores[k] is the score for a vertex of degree k.)
>
> The score of a graph is the sum of the scores of all its vertices.
>
> Given N and scores[], calculate the maximum possible score of all the
> graphs in S(N).
>
If both n and the scores are given, then the maximum and only possible 
score is the sum of the scores.  Is the problem to find the maximum score
of a simple (no loops, no double edges, no directed edges) connected graph 
of n-vertices?

The degree of a graph is two times the number of edges
and the maximum number of edges for a simple graph is
a complete simple graph which has n(n - 1)/2 edges.
Thus the maximum degree of a simple connected graph of n
vertices is n^2 - n.

> One of the top rated programmers in the world wrote up a very similar
> solution to the following in less a minute...
>
It appears to be recursive programming, ie a routine that repeatedly calls 
itself until an exit condition is meet.

> int solve(int N, int scores[])
> {
> 	int X[110][210];
> 	memset(X, 0xc0, sizeof(X)); // set X[a][b] all negative
>
> 	X[0][0] = 0;
>
> 	for (int i = 0; i < N; i++)
> 		for (int j = 0; j <= N * 2 - 2; j++)
> 			for (k = 1; k < N; k++)
> 			{
> 				int candidate = X[i][j] + scores[k];
>
> 				// if candidate is higher than X[i+1][j+k], overwrite it
> 				if (X[i+1][j+k] < candidate)
> 					X[i+1][j+k] = candidate;
> 			}
>
> 	return X[N][N*2-2];
> }
>
> Clearly they are using some kind of dynamic programming / memoization
> technique - but I don't really understand it all.
>
> Can anyone see what precisely X[a][b] holds?  Any what do i, j and k
> represent?  What property of graphs are they using for the "optimal
> substructure"?
>
> Is this type of solution part of a general class of solutions?  and if
> so can anyone recommend a good textbook or site that would cover it?
>
> Thanks,
> Andrew.
>

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Help with graph theory puzzle solution analysis Andrew Tomazos <andrew@tomazos.com> - 2011-12-17 14:23 -0800
  Re: Help with graph theory puzzle solution analysis William Elliot <marsh@rdrop.com> - 2011-12-17 20:37 -0800
    Re: Help with graph theory puzzle solution analysis Wes Groleau <Groleau+news@FreeShell.org> - 2011-12-18 00:28 -0500
  Re: Help with graph theory puzzle solution analysis Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-12-17 22:56 -0600

csiph-web