Let $G(V, E)$ be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path.

Let $s \in V$ be a vertex in $G$. For every $u \in V$ and for every $k \geq 0$, let $d_k(u)$ denote the weight of a shortest path (in terms of weight) from $s$ to $u$ of length at most $k$. If there is no path from $s$ to $u$ of length at most $k$, then $d_k(u)=\infty$.

Consider the statements:

S1: For every $k \geq 0$ and $u \in V, d_{k+1}(u) \leq d_k(u)$.

S2: For every $(u, v) \in E$, if $(u, v)$ is part of a shortest path (in terms of weight) from $s$ to $v$, then for every $k \geq 0, d_k(u) \leq d_k(v)$.

Which one of the following options is correct?

Let G(V, E) be a directed graph, where V = {1, 2, 3, 4, 5} is the set of vertices and E is the set of directed edges, as defined by the following adjacency matrix A.

$$A[i][j] = \left\{ {\matrix{ {1,} & {1 \le j \le i \le 5} \cr {0,} & {otherwise} \cr } } \right.$$

A[i][j] = 1 indicates a directed edge from node i to node j. A directed spanning tree of G, rooted at r $$\in$$ V, is defined as a subgraph T of G such that the undirected version of T is a tree, and T contains a directed path from r to every other vertex in V. The number of such directed spanning trees rooted at vertex 5 is _____________.

Consider the following directed graph: 

Which of the following is/are correct about the graph?

Define R_n to be the maximum amount earned by cutting a rod of length n meters into one or more pieces of integer length and selling them. For i > 0, let p[i] denotes the selling price of a rod whose length is i meters. Consider the array of prices:

p[1] = 1, p[2] = 5, p[3] = 8, p[4] = 9, p[5] = 10, p[6] = 17, p[7] = 18

Which of the following statements is/are correct about R₇?