Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!goblin2!goblin.stu.neva.ru!feeder3.cambriumusenet.nl!feed.tweaknews.nl!postnews.google.com!news1.google.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.scnresearch.com!news.scnresearch.com.POSTED!not-for-mail NNTP-Posting-Date: Sat, 17 Dec 2011 22:37:40 -0600 Newsgroups: comp.programming,comp.theory,sci.math,comp.graphics.algorithms Date: Sat, 17 Dec 2011 20:37:37 -0800 From: William Elliot Subject: Re: Help with graph theory puzzle solution analysis In-Reply-To: Message-ID: <20111217201224.H69688@agora.rdrop.com> References: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Lines: 75 X-Usenet-Provider: http://www.giganews.com NNTP-Posting-Host: 199.26.172.34 X-AuthenticatedUsername: NoAuthUser X-Trace: sv3-hxNPQLXlAQ3BPY+Ck9rajurzq8FOMX2ryoQ1PN2+M63FRvFB1Euc3jpYUJSGVi8wRTp/b/h+r6IfSD5!xQIurAMM0y7P5wHeZ/DVagOI3rlPtrsI4WXyqR4fZ8VgmYhw5UMLrNfDIvxK/clAuGzkP2hlYkQu!ygWLwNJg X-Complaints-To: abuse@scnresearch.com X-DMCA-Complaints-To: abuse@scnresearch.com X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40 X-Original-Bytes: 3746 Xref: x330-a1.tempe.blueboxinc.net comp.programming:1111 comp.theory:1478 comp.graphics.algorithms:665 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. >