Author |
Topic: Graph, Weights and Averages (Read 1384 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Graph, Weights and Averages
« on: Oct 8th, 2010, 3:16am » |
 Quote  Modify
|
A connected graph is given. To some of its nodes weights are assigned.
Prove that it is always possible to assign a weight to every remaining node that is equal to the average weight of all nodes connected to it.
Prove that this assignment is always unique.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Graph, Weights and Averages
« Reply #1 on: Oct 8th, 2010, 4:51am » |
Quote Modify
|
Wow, it's been a while..
Don't you just get subsets of K linear equations with K unknowns? Gaussian elimination would give a unique answer, wouldn't it?
|
| « Last Edit: Oct 8th, 2010, 4:56am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: Graph, Weights and Averages
« Reply #2 on: Oct 8th, 2010, 10:00am » |
Quote Modify
|
on Oct 8th, 2010, 4:51am, towr wrote:Wow, it's been a while..
Don't you just get subsets of K linear equations with K unknowns? Gaussian elimination would give a unique answer, wouldn't it? |
|
Systems of linear equations don't always have (unique) solutions For example, take any pair of:
x+y=1
x+y=2
2x+2y=2
A graph with no given values (or an isolated connected component of a disconnected graph with no given values) also gives rise to k linear equations in k unknowns, but has multiple solutions.
Considering the graph as a system of linear equations may help frame a proof, but it still leaves both existence and uniqueness to be proven...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print