Summative graphs

[Dratino]

Define a summative graph as one where each vertex has a value, and each edge connecting two vertices has a value equal to the sum of the values of the two vertices that it connects.

Now, I have the following question: given a graph with the edge values but not the vertex values, in what situations (i.e. what types of graphs) could you deduce the vertex values from the edge values, given that it was a summative graph?

I've got that you can deduce the numbers from any odd cycles in the graph (for obvious reasons; try a system of equations), but I still haven't managed to preclude any graphs that don't have any odd cycles from being uniquely identifiable. None of the ones that I've tried do, but then again, that's a very limited set. The most complex non-even-cycle one I've tried is a cube. (Trees are obviously non-unique.)

(I'd also like to know whether there are any similar constructions out there.)

[Tony]

Bipartite graphs don't have any odd cycles -- http://en.wikipedia.org/wiki/Bipartite_graph but I imagine that some can be constructed to be solvable.

[Dratino]

Dratino @ Tue Apr 12, 2011 6:41 pm wrote:

The most complex non-even-cycle one I've tried is a cube. (Trees are obviously non-unique.)

Urgh. I meant "non-odd-cycle".

But yeah, bipartite graphs. I imagine there's some sort of proof that graphs of that nature never have unique solutions.

There are also other classifications, such as ones that can have solutions but will not always have solutions - some sets of edge-values will lead to contradictions (such as a square with edge-values 17, 24, 15, and 19 going in order from one point to the next). Others can have contradictions, but will always have unique solutions when they do have solutions (such as two triangles connected together by a single edge).

[DemonWasp]

You have a system of equations with V unknowns (one unknown per vertex). You have E equations (one per edge) of the form v_i + v_j = e_ij for e_ij element-of E.

I seem to recall something about a system of N equations in M < N variables being solvable from those equations (however difficult that proves to be).

I think if you add those two paragraphs together you'll have your answer. I could be totally off-base, of course; it's been a while since I did any formal mathematics (and, when I did, I generally came close to failure).

[Dratino]

I don't think that will work. For example, a square is a non-solvable summative graph.

Given that a+b = 12, b+c = 15, c+d = 19, and a+d = 16, you still can't solve for the individual numbers. There are still infinitely many solutions.

I do know what you're getting at; but it was cases like these (the square) that led me to ponder about the graphs, because it's not always the case that N equations and M < N unknowns are solvable.

Actually, that's a bad case because M = N; consider instead a hexagon, with a diagonal going straight through the middle. You have the equations:

a + b = 16
b + c = 20
c + d = 15
d + e = 9
e + f = 13
f + a = 15
b + e = 19

6 unknowns, 7 equations. And yet I can find you at least two distinct solutions (a, b, c, d, e, f):

(7, 9, 11, 4, 5, 8) and (3, 13, 7, 8, 1, 12) are both valid solutions.

In fact, I can construct a system of equations with 12 equations and 8 variables that still has infinitely many solutions - a cube.

The reason for this is because some of the equations can be derived from others, and therefore are trivial. In the case above with the square, you can get the value of one of the edges given the other three.

So, the question can also be phrased as: what edge values are deducible given a graph?

[DemonWasp]

I think you meant b + e = 14, not 19.

I remember now: my second paragraph in the previous post only applies if all the equations are linearly independent. I'm not sure how to apply that to a graph.

Your existing system has:
a + f == ( a + b ) - ( b + c ) + ( c + d ) - ( d + e ) + ( e + f ) == 16 - 20 + 15 - 9 + 13 = 15, so equation 6 is linearly dependent on the previous ones and doesn't "contribute" to solving the puzzle.

It is worth noting that this linear dependence will occur whenever there is a cycle. I don't know whether it ever occurs otherwise. If you could find a way to cound all the occurrences of linear dependence easily, you could determine the proper values to compare for (number of equations) versus (number of unknowns).

[Dratino]

Well, it doesn't occur for odd cycles. For example, a pentagon will always have a unique solution.

So what I mean is, is there a way to prove that this linear dependence exists for certain edges?

[chopperdudes]

from what we've just learnt, these could be solved with lin alg. set up the equation in AX = B form and form the augmented matrix [A|B]. if B is not in the column space of A then there are no solutions, if B is in the column space of A and rank A = rank A|B = n (for m x n matrices) then you will get a unique solution. if A is not full rank you'll always have infinitely many solutions.

so to solve it, you'd first want to make sure there is a unique solution, then gaussian eliminate the A|B matrix.

now to actually implement this.. heh...

i'd first check if A is full rank, and therefore invertible, straightforward way would be to just plug in the Laplace expansion, although that becomes impractical once you have more than say 9 equations... i would prolly just write a gaussian elimination algo for a 2D array and check if the diagonals are all 1's... (of course check size of matrix first, fat matrix you'll know right away, skinny matrix check for lin dep)

on the top of my head ...
...
...
...
actually nvm why not just gaussian eliminate [A|B] right off the bat? from the reduced row-echelon form you can pretty much determine how many solutions that system has.