retagged by
6,982 views
15 votes
15 votes

In a directed acyclic graph with a source vertex $\textsf{s}$, the $\textit{quality-score}$ of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex $v$ other than $\textsf{s}$, the quality-score of $v$ is defined to be the maximum among the quality-scores of all the paths from $\textsf{s}$ to $v$. The quality-score of $\textsf{s}$ is assumed to be $1$.

The sum of the quality-scores of all vertices on the graph shown above is _______

retagged by

3 Answers

Best answer
13 votes
13 votes

Let $Q(v)$ denote the quality-score of vertex $v.$

  1. $Q(s) = 1$
  2. $Q(c) = 1*1\; (s \overset{1}{\rightarrow } c)$
  3. $Q(f) = 1 * 1*9=9\; (s  \overset{1}{\rightarrow} c  \overset{9}{\rightarrow} f)$
  4. $Q(a) = 1 * 9=9\; (s  \overset{9}{\rightarrow}a)$
  5. $Q(d)= 1 * 9* 1=9\; (s  \overset{9}{\rightarrow} a  \overset{1}{\rightarrow}  d)$
  6. $Q(g)= 1 * 9* 1*9=81\; (s  \overset{9}{\rightarrow} a  \overset{1}{\rightarrow}  d\overset{9}{\rightarrow}  g)$
  7. $Q(b) = 1 * 9*1=9\; (s  \overset{9}{\rightarrow}a\overset{1}{\rightarrow}  b)$
  8. $Q(e)= 1 * 9* 1*9=81\; (s  \overset{9}{\rightarrow} a  \overset{1}{\rightarrow}  d\overset{9}{\rightarrow}  e)$
  9. $Q(t)= 1 * 9* 1*9*9=729\; (s  \overset{9}{\rightarrow} a  \overset{1}{\rightarrow}  d\overset{9}{\rightarrow}  e\overset{9}{\rightarrow}  t)$

Therefore, the sum of the quality-scores of all vertices on the graph $ = 2\times 1 + 4\times 9 + 2 \times 81 + 729 = 929.$

selected by
5 votes
5 votes
S = 1 (Given)

C = 1 (S $\rightarrow$ C)

F = 1 * 9 (S  $\rightarrow$ C  $\rightarrow$ F)

A = 9 (S  $\rightarrow$ A)

D = 9*1 (S  $\rightarrow$ A  $\rightarrow$ D)

G = 9 * 1 * 9 (S  $\rightarrow$ A  $\rightarrow$ D  $\rightarrow$ G)

B = 9 * 1 (S  $\rightarrow$ A  $\rightarrow$ B)

E = 9 * 1 * 9 (S  $\rightarrow$ A  $\rightarrow$ D  $\rightarrow$ E)

T = 9*1*9*9 (S  $\rightarrow$ A  $\rightarrow$ D  $\rightarrow$ E $\rightarrow$ T)

 

Sum of quality-score of all vertices = 1+1+9+9+9+81+9+81+729 = 929
2 votes
2 votes
Applying reverse of DJKstra will also work. i.e, Instead of selecting respective min adjacent, choose respective max adjacent
Answer:

Related questions

1 votes
1 votes
2 answers
4
admin asked Dec 15, 2022
692 views
What is the minimum number of nodes required in a DAG (Directed Acyclic Graph) for the following block?\[\begin{aligned}U=Z & =V+W \\X=Y & =U+1 \\A & =X+Y\end{aligned}\]