Author |
Topic: Centers of the tree (Read 449 times) |
|
alexeigor
Newbie
Posts: 45
|
 |
Centers of the tree
« on: Mar 20th, 2008, 1:20pm » |
 Quote  Modify
|
Given tree. Vertex v is center of the tree if the distance from v to u (arbitrary vertex of the tree) is mininimal. Weights of edges is equal.
Find all centers of the tree.
For ex:
1 2
2 3
Answer:
2
|
| « Last Edit: Mar 20th, 2008, 1:37pm by alexeigor » |
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
|
Re: Centers of the tree
« Reply #1 on: Mar 20th, 2008, 4:21pm » |
Quote Modify
|
I seem to recollect the following:
Remove zero (typo!) degree one nodes, and repeat. In the end you are either left with 1 or 2 nodes which form the center.
Probably not very efficient... (depends on the representation though)
|
| « Last Edit: Mar 21st, 2008, 10:23am by Aryabhatta » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print