0
$\begingroup$

Given a Undirected Weighted Planar Graph with $N$ nodes and $N-1$ edges each having different weight $w$. Between two nodes there is exactly one path that goes through the edges and nodes such that no node appears in the path more than once.

Given some nodes $A$1, $A$2$, ...,A$ K. $2$ nodes are taken at random from these nodes.

How to calculate the distance between those two randomly chosen nodes ?( The answer will be in a form of rational numbers)

By the way, I tried taking all pairs of points in the list $A$1, $A$2$, ...,A$ K and added sum of the distances between them i.e $(k*(k-1))/2$ pairs and divided it by K i.e. total number of points in the list. But this gives wrong answer. It is giving more in numerator.

$\endgroup$
  • $\begingroup$ Your Graph is a tree and “between two nodes there is exactly one path that goes through the edges and nodes such that no node appears in the path more than once” so the length of this path is the unweighted distance between these two nodes and a sum of weights of edges of this path is the weighted distance between these two nodes. $\endgroup$ – Alex Ravsky Nov 7 '16 at 8:39
  • $\begingroup$ So, which value are you asking for? For the expectation of a weighted distance between two nodes which are taken at random from the given nodes $A_1,\dots, A_k$? Then the answer depends on the graph shape, weight of its edges, the given set of nodes and on the probability of the random choice of each pair of the given nodes. $\endgroup$ – Alex Ravsky Nov 7 '16 at 8:39
  • $\begingroup$ @AlexRavsky Yes, I'm asking for the expectation of a weighted distance between two nodes which are taken at random from the given nodes $A_1,…,A_k $. Is there some algorithm given the shape,weight and list of $k$ nodes ? $\endgroup$ – sammy Nov 7 '16 at 19:22
2
$\begingroup$

Without specific conditions imposed on the shape of the graph $G$, weights $w_e$ of its edges $e$, the given set $\{A_1,\dots, A_k\}$ of nodes and on the probability $p_{ij}$ (for $i<j$) of the random choice of each pair $\{A_i, A_j\}$ of the given nodes I can propose a straightforward algorithm, which has a complexity polynomial with the respect to the number of nodes of the graph $G$.

First of all we do a preprocessing which calculates the weighted distance $d_w(v,u)$ between each pair $v$ and $u$ of nodes of the graph $G$. This can be done recursively as follows. Let $v$ be a leaf of the graph $G$. Calculate the weighted distances between each pair of nodes of the induced graph $G - v$. Let $u$ be a unique neighbor of the node $v$. For each node $u’$ of the graph $G- v$ put $$d_w(u’,v)= d_w(u’,u)+w(u,v).$$

Now the expectation which you are asking for is

$$\sum_{1\le i<j\le K} p_{ij}d_w(A_i,A_j).$$

Update. In particular, if “2 nodes are taken at random from these nodes” means that the pair $\{A, B\}$ of the given (not necessarily distinct) nodes is constructed by independently picking nodes $A$ and $Bj$ such that each of them has a probability $r_i=P\{A=A_i\}= P\{B=B_i\}$ (in particular, for the uniform distribution $r_i=1/K$) then $p_{ii}=r_i^2$ (anyway, we don’t sum weighted distances $d_w(A_i,A_j)$ because they are zero) and $p_{ij}=2r_ir_j$ if $i<j$.

$\endgroup$
  • $\begingroup$ Let's say we have this graph {(1 3 1),(2 3 2),(3 4 3),(4 5 4),(4 6 5)} where first and second point represent u,v and third one is the weight .And I have to choose from these (1,2,3,4,5,6) nodes .What is the answer ? Is it 87/15 $\endgroup$ – sid597 Nov 8 '16 at 9:17
  • $\begingroup$ @johnsmith Yes, provided all $p_{ij}$ are equal. $\endgroup$ – Alex Ravsky Nov 8 '16 at 10:06
  • $\begingroup$ Why would all $p_{ij}$ not be same ? I mean they all have same probability of being selected 1/15 .And the answer to this problem is 29/6 according to the tester $\endgroup$ – sid597 Nov 8 '16 at 10:16
  • $\begingroup$ @johnsmith 1.'Which is a probability that when we'll get out of the room we'll meet a crocodile? It is $1/2$, because we either meet it or not’ 2. Since $87/15=29/5$, probably, there is a misprint. $\endgroup$ – Alex Ravsky Nov 8 '16 at 10:32
  • $\begingroup$ I think the probability of selecting one pair will be 2/36 because there are 36 pairs and we need to find the pair with the given condition $\endgroup$ – sid597 Nov 8 '16 at 11:01
1
$\begingroup$

If your question involves two different people picking the two nodes, then every pair $(u,v)$ that you pick should be treated as an ordered pair. So you should add the weights between every pair and multiply it by $2$. This will give you the numerator. Also, the denominator will be $(2*{n \choose 2} + n)$. The additional $n$ corresponds to the fact that both of them might choose the the same node(in such cases $d(u,v)$ will be $0$, so they won't affect the numerator). For the above example data, your numerator will be $87*2=174$ and the denominator will be $2*15 + 6 = 36$. This, on reduction to simplest form will give you ${29 \over 6}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.