Discrete Integral and Discrete Derivative on Graphs and Switch Problem of Trees

Abstract

For a vertex and edge weighted (VEW) graph $G$ with a vertex weight function $f_G$ let $W_{\alpha ,\beta }\left(G\right)=\sum _{\left\{u,v\right\}\subseteq V\left(G\right)}\left[\alpha f_G\left(u\right)\times f_G\left(v\right)+\beta (f_G\left(u\right)+f_G\left(v\right))\right]d_G\left(u,v\right)$ where, $\alpha ,\beta \in ℝ$ and $d_G\left(u,v\right)$ denotes the distance, the minimum sum of edge weights across all the paths connecting $u,v\in V\left(G\right)$. Assume $T$ is a VEW tree, and $e\in E\left(T\right)$ fails. If we reconnect the two components of $T-e$ with new edge $ϵ\ne e$ such that, $W_{\alpha ,\beta }\left(T_{ϵ\backslash e}=T-e+ϵ\right)$ is minimum, then $ϵ$ is called a best switch (BS) of $e$ w.r.t. $W_{\alpha ,\beta }$. We define three notions: convexity, discrete derivative, and discrete integral for the VEW graphs. As an application of the notions, we solve some BS problems for positively VEW trees. For example, assume $T$ is an $n$-vertex VEW tree. Then, for the inputs $e\in E\left(T\right)$ and $w,\alpha ,\beta \in {ℝ}^{+}$, we return $ϵ$, $T_{ϵ\backslash e}$, and $W_{\alpha ,\beta }\left(T_{ϵ\backslash e}\right)$ with the worst average time of $O(\log n)$ and the best time of $O\left(1\right)$ where $ϵ$ is a BS of $e$ w.r.t. $W_{\alpha ,\beta }$ and the weight of $ϵ$ is $w$.

1. Introduction and Notations

Unlike Euclidean space, which is equipped with coordinate systems, we cannot stay at a network node and visualize where we are and how to achieve our goal. On the other hand, analyzing a network using local information can lower the cost of tasks [1,2,3,4,5,6]. Preprocessing may help to establish a network coordinate for local tasks and reach the destination step by step.

This paper defines discrete derivative, discrete integral, and convexity notions for vertex and edge-weighted graphs, which will help with local tasks. To do that, we choose the common definition of distance for edge-weighted graphs in the literature, which can be generalized or modified to satisfy metric properties. Applying the notions above, we design and solve some tree-related problems.

Unless otherwise stated, we assume a graph is weighted (vertices and edges) and connected without loops or multiple edges. Then, by saying that a graph $G$ is $\left(f_G,w_G\right)$-weighted, the vertex weight function is $f_G$ and the edge weight function is $w_G$. The weight of a path $P_G\left(v_1,v_n\right)=v_1{v}_2\dots v_n$ in $G$ is $\sum _{i=1}^{n-1}{w}_G\left(v_i{v}_{i+1}\right)$. And $d_G\left(u,v\right)$ denotes the distance between $u,v\in V\left(G\right),$ that is, the weight of the minimum weight paths across all the paths connecting $u$ and $v$. Note that the distance of a vertex with itself is zero, and the distance between two vertices is infinite if they are not connected with a path. By saying a graph is positively weighted, we mean both vertex and edge weights are positive. We define the following numerical invariant for a $\left(f_G,w_G\right)$-weighted graph $G$,

$$W_{\alpha ,\beta }\left(G\right)={{\displaystyle \sum }}_{\left\{u,v\right\}\subseteq V\left(G\right)}\left[\alpha f_G\left(u\right)\times f_G\left(v\right)+\beta (f_G\left(u\right)+f_G\left(v\right))\right]d_G\left(u,v\right), \alpha ,\beta \in ℝ.$$

And for $A, B\subseteq V\left(G\right)$, and $v\in V\left(G\right)$, we define

$$f_G\left(A\right)={\displaystyle \sum }_{x\in A}{f}_G\left(x\right), {\sigma }_G\left(v\right)={\displaystyle \sum }_{x\in V\left(G\right)}{d}_G\left(v,x\right), h_G\left(v\right)={\displaystyle \sum }_{x\in V\left(G\right)}{f}_G\left(x\right)d_G\left(v,x\right),$$

$$d_G\left(A,B\right)={\displaystyle \sum }_{a \in A}{\displaystyle \sum }_{b \in B}{d}_G\left(a,b\right).$$

And for the given subgraphs $H$ and $K$ of $G$, let:

$$d_G\left(H,K\right)={\displaystyle \sum }_{u \in V\left(H\right)}{\displaystyle \sum }_{v \in V\left(K\right)}{d}_G \left(u,v\right), f_G\left(H\right)={\displaystyle \sum }_{a\in V\left(H\right)}{f}_G\left(a\right).$$

Definition 1.

For a tree $T$ and $uv\in E\left(T\right)$, $T-\{uv$} has two components. We name the components $T_u^v$ and $T_v^u$ with $u\in V\left(T_u^v\right)$ and $v\in V\left(T_v^u\right)$ . As an extension for the later notation to subtrees, if $xy\in V(T_u^v)$, $[T_u^v]{ }_x^y$ and $[T_u^v]{ }_y^x$ denotes the components of $T_u^v-\left\{xy\right\}$ and so on. Also, set $n_T\left(T_u^v\right)=\left|V\left(T_u^v\right)\right|$ and $n_T\left(T_v^u\right)=\left|V\left(T_v^u\right)\right|$.

By Definition 1 $V\left(T\right)=V\left(T_u^v\right){\displaystyle \cup }V\left(T_v^u\right)$ and $n_T\left(T_u^v\right)+n_T\left(T_v^u\right)=\left|V\left(T\right)\right|$. We remind the reader that $N_G\left(x\right)$ denotes a vertex $x$′s neighbors.

Using the above notation for a tree $T$ let, $N_T={\{(n_T\left(T_u^v\right),n_T\left(T_v^u\right))\}}_{uv\in E\left(T\right)}$ and $F_T={\left\{\left(f_T\left(T_u^v\right),f_T\left(T_v^u\right)\right)\right\}}_{uv\in E\left(T\right)}$. For more detail $n_T\left(T_u^v\right)$ and $n_T\left(T_v^u\right)$ are the number of vertices in $T_u^v$ and $T_v^u$, respectively. And $f_T\left(T_u^v\right)$ and $f_T\left(T_v^u\right)$ are the total weight of vertices in $T_u^v$ and $T_v^u$, respectively.

For ease and based on the definition of $W_{\alpha ,\beta }$, we define two more distance-based numerical graph invariants for a $\left(f_G,w_G\right)$-weighted graph $G$ as follows:

$$W_{\times }\left(G\right)={{\displaystyle \sum }}_{\left\{u,v\right\}\subseteq V\left(G\right)}\left[f_G\left(u\right)\times f_G\left(v\right)\right]d_G\left(u,v\right),$$

$$W_{+}\left(G\right)={{\displaystyle \sum }}_{\left\{u,v\right\}\subseteq V\left(G\right)}\left[f_G\left(u\right)+f_G\left(v\right)\right]d_G\left(u,v\right).$$

Indeed, $W_{1,0}\left(G\right)=W_{\times }\left(G\right)$, $W_{0,1}\left(G\right)=W_{+}\left(G\right)$ and $W_{\alpha ,\beta }\left(G\right)=\alpha W_{\times }\left(G\right)+\beta W_{+}\left(G\right)$.

Using the notations, the coordinate of $T$ is shown and defined with

$$Q_T=\left\{F_T,N_T,W_{\times }\left(T\right),W_{+}\left(T\right)\right\}$$

Assume $T$ is a $\left(f_T,w_T\right)$-weighted tree and $e\in E\left(T\right)$. If $e$ fails (removed from the edge set), then we have $T-e$ that has two components. If we reconnect the two components of $T-e$ with an edge, $ϵ$, we have $T+ϵ-e$. For ease, we will denote $T+ϵ-e$ by  $T_{ϵ\backslash e}$. Then $ϵ$ is called a switch of $e$ and the tree $T_{ϵ\backslash e}$ is called a switch. Moreover, if $e\ne ϵ$ and $W_{\alpha ,\beta }\left(T_{ϵ\backslash e}\right)$ is minimum, $ϵ$ is called a best switch (BS) of $e$ w.r.t. $W_{\alpha ,\beta }$. Note that $T_{ϵ\backslash e}$ is a tree, $e\in E\left(T\right)$, and $ϵ\in E\left(T^c\right)$.

Now suppose $T$ is an $n$-vertex and positively weighted tree with coordinate $Q_T$. We are interested in solving the following problem. Get $T$, $Q_T$, $e\in E\left(T\right)$ and $w,\alpha ,\beta \in {ℝ}^{\ge 0}$ and return $T_{ϵ\backslash e}$, $Q_{T_{ϵ\backslash e}}$, $ϵ$ and $W_{\alpha ,\beta }\left(T_{ϵ\backslash e}\right)$, where $ϵ$ is a BS of $e$ w.r.t. $W_{\alpha ,\beta }$ and $w=w_{T_{ϵ\backslash e}}\left(ϵ\right)$. (by $w,\alpha ,\beta \in {ℝ}^{\ge 0}$ we mean $w>0, \alpha +\beta >0$, $\alpha \ge 0$, and $\beta \ge 0$). We solve the problem with the worst average time of $O\left(\log n\right)$ and the best average time of $O\left(1\right)$. Clearly, using the output of the problem, if we solve the problem with some complexities, we can keep getting $e_i$ and $w_{i+1},{\alpha }_{i+1},{\beta }_{i+1}\in {ℝ}^{\ge 0}$ and solve the problem on ${\left({(T_{{ϵ}_1\backslash e_1})}_{{ϵ}_2\backslash e_2}\dots \right)}_{{ϵ}_i\backslash e_i}$ with the same complexities on $T$, $i>1$. Changing edge weights within the positive range are also supported in $O\left(1\right)$-time per change to update the coordinates $Q_{T_{{ϵ}_i\backslash e_i}}$ at any meaningful stage. The mentioned problem is the primary example that will solve in the application section as an application of our tools in the following section. The problem can be seen as a generalization of [7,8,9] that has found some applications [6,10,11,12]. For some relevant optimization problems over spanning trees, see [13,14,15,16,17,18,19]. This paper uses extensive notation for more precise interaction, which may take some time to get used to. But our solutions are natural, utilizing some calculus intuition behind the notations.

We might be able to partially compare our solution for the above problem with top tree methods [7,8,9] (see the final section). Generalizing the top tree method solves the problem above for some specified edges and fixed $\alpha ,\beta$ with the same average complexity as our solution. However, by changing $\alpha ,\beta ,$ in the top tree method, one needs to repeat the preprocessing, which is expensive. We also compare our method to the swap edge problem of spanning trees [20,21], which requires a conversion. See the last section for more details.

As the main topics of this paper, we have the following sections. We will define some concepts and achieve some results. Applying the results, we find an efficient solution for BS of positively weighted trees mentioned above. Our method is general, and we have applied it to other problems [22].

2. Discrete Derivative and Integral

Discrete derivative, discrete integral, and convexity are three intuitive concepts for weighted graphs that we define in this section. We have some results and general examples specifically for trees.

Definition 2.

Suppose $G$ is a $\left(f_G,w_G\right)$-weighted graph. The discrete derivative of a vertex $a\in V\left(G\right)$ toward $x\in N_G\left(v\right)$ is defined and denoted as follows:

$$f_G^{\prime }\left(\overrightarrow{ax}\right)=\{\begin{array}{cc}\frac{f_G\left(x\right)-f_G\left(a\right)}{d_G\left(x,a\right)}\hspace{1em}\hspace{1em}& d_G\left(x,a\right)\ne 0,\\ f_G\left(x\right)-f_G\left(a\right)\hspace{1em}\hspace{1em}& d_G\left(x,a\right)=0.\end{array}$$

(1)

We say $f_G^{\prime }$ is consistent if $d_G\left(x,a\right)=0$ results in $f_G^{\prime }\left(\overrightarrow{ax}\right)=0$, $ax\in E\left(G\right)$.

Using Figure 1 as graph $G$, $f_G^{\prime }\left(\overrightarrow{\mathrm{a}x}\right)=\frac{4-3}{3}=\frac{1}{3}$ where $d_G\left(x,\mathrm{a}\right)=3$. And $f_G^{\prime }\left(\overrightarrow{x\mathrm{a}}\right)=\frac{3-4}{3}=-\frac{1}{3}$.

Lemma 1.

Assume $f_1$ and $f_2$ are two vertex weight functions for a graph. If $f=\alpha f_1+\beta f_2$, then $f^{\prime }=\alpha f_1^{\prime }+\beta f_2^{\prime }$, where $\alpha ,\beta \in ℝ$. Moreover, if $f_1$ an $f_2$ are consistent, then $f$ also is.

A path, $v_1{v}_2\dots v_n$, is called $f_G$-decreasing if it is a path and

$$f_G\left(v_{i+1}\right)<f_G\left(v_i\right), 0<i<n.$$

An increasing path is defined in the same sense. Clearly, if $v_1{v}_2\dots v_n$ is a $f_G$-decreasing path and edge weights are positive, then $f_G^{\prime }\left(\overrightarrow{v_i{v}_{i+1}}\right)<0$, $0<i<n$.

Definition 3.

Suppose $G$ is a $\left(f_G,w_G\right)$-weighted graph. Then, $v\in V\left(G\right)$ is called $f_G$-Root or $f_G$-Roof of $G$ if $f_G\left(v\right)$ is minimum or maximum, respectively. Let $A\subset V\left(G\right)$ is the set of $f_G$-Roots ($f_G$-Roofs) of $G$. Then we say $G$ is $f_G$-convex (concave) if and only if for every $v\in V\left(G\right)$ there is a decreasing (increasing) path from $v$ to some $a\in A$.

Whenever there is no confusion, we may use Root instead of, $f_G$-Roots, etc. Using the above image, the vertex with weight 0 is a Root, and the vertex with weight 4 is a Roof in the depicted graph.

To employ discrete derivatives as a tool, we first create some induced weight functions using the current weight of the graph for the vertices of an $\left(f_G,w_G\right)$-weighted graph, $G$. The first one is as follows:

$${\sigma }_G:V\left(G\right)\to ℝ \mathrm{S}.\mathrm{t}. {\sigma }_G\left(v\right)={\displaystyle \sum }_{x\in V\left(G\right)}{d}_G\left(v,x\right), v\in V\left(G\right)$$

Let $T$ be a $\left({\sigma }_T,w_T\right)$-weighted tree (the vertex-weight function is, ${\sigma }_T$). If  $ax\in E\left(T\right)$ and $w_G\left(ax\right)=0$, then ${\sigma }_T^{\prime }\left(\overrightarrow{ax}\right)=0$, otherwise:

$${\sigma }_T^{\prime }\left(\overrightarrow{ax}\right)=\frac{{\sigma }_T\left(x\right)-{\sigma }_T\left(a\right)}{d_T\left(x,a\right)}=\frac{{\sigma }_T\left(x\right)-{\sigma }_T\left(a\right)}{w\left(ax\right)}=n_T\left(T_a^x\right)-n_T\left(T_x^a\right).$$

(2)

Because

$${\sigma }_T\left(x\right)-{\sigma }_T\left(a\right)=w\left(ax\right)\left[n_T\left(T_a^x\right)-n_T\left(T_x^a\right)\right].$$

(3)

Another vertex-weight function for $G$ is induced using the primary weight functions as follows:

$$h_G:V\left(G\right)\to ℝ \mathrm{S}.\mathrm{t}. h_G\left(v\right)={\displaystyle \sum }_{x\in V\left(G\right)}{f}_G\left(x\right)d_G\left(v,x\right), v\in G.$$

To help with the computation of $h_T^{\prime }$s for a $\left(h_T,w_T\right)$-weighted tree $T$, let $a\in V\left(T\right)$ and $x$ be an $a$′s neighbor. Thus,

$$h_T\left(a\right)={\displaystyle \sum }_{v\in V\left(T_a^x\right)}{f}_T\left(v\right)d_T\left(a,v\right)+{\displaystyle \sum }_{v\in V\left(T_x^a\right)}{f}_T\left(v\right)[d_T\left(x,v\right)+w\left(ax\right)],$$

$$h_T\left(x\right)={\displaystyle \sum }_{v\in V\left(T_a^x\right)}{f}_T\left(v\right)[d_T\left(a,v\right)+w\left(ax\right)]+{\displaystyle \sum }_{v\in V\left(T_x^a\right)}{f}_T\left(v\right)d_T\left(x,v\right).$$

(4)

Using the above equations, $h_T\left(x\right)-h_T\left(a\right)=w\left(ax\right)\left[f_T\left(T_a^x\right)-f_T\left(T_x^a\right)\right]$. Therefore, if $w_T\left(ax\right)=0$, then $h_T^{\prime }\left(\overrightarrow{ax}\right)=0$, otherwise:

$$h_T^{\prime }\left(\overrightarrow{ax}\right)=\frac{h_T\left(x\right)-d_T\left(a\right)}{d_T\left(x,a\right)}=\frac{w\left(ax\right)\left[f_T\left(T_a^x\right)-f_T\left(T_x^a\right)\right]}{w\left(ax\right)}=f_T\left(T_a^x\right)-f_T\left(T_x^a\right).$$

(5)

Using Equations (3) and (4), $h_T^{\prime }$ and ${\sigma }_T^{\prime }$ are consistent for any tree $T$.

Let $N_T={\{(n_T\left(T_u^v\right),n_T\left(T_v^u\right))\}}_{uv\in E\left(T\right)}$ and $F_T={\left\{\left(f_T\left(T_u^v\right),f_T\left(T_v^u\right)\right)\right\}}_{uv\in E\left(T\right)}$. Using Equations (2) and (5), $F_T$, and $N_T$, one can compute ${\sigma }_T^{\prime }$ and $h_T^{\prime }$ easily. If $f_T\left(v\right)=1$ for every $v\in V\left(T\right),$ then $\left(f_T\left(T_u^v\right),f_T\left(T_v^u\right)\right)=\left((n_T\left(T_u^v\right),n_T\left(T_v^u\right)\right)$ for every $uv\in E\left(T\right)$. The following algorithm extracts $F_T$ for a tree $T$, starts with the edges adjacent to a leaf and then deletes the leaves at each step until the edge set is empty. It is linear regarding the number of vertices and uses the fact that for every $uv\in E\left(T\right)$ (Algorithm 1):

$$f_T\left(T_u^v\right)+f_T\left(T_v^u\right)=f_T\left(T\right),\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{f}_T\left(T_v^u\right)=f_T\left(v\right)+{\sum }_{x\in N_T\left(v\right)\backslash u}{f}_T\left(T_x^v\right).$$

Algorithm 1 Computing $F_T$ or $N_T$

Input: Adjacency list of an $n$-vertex, nontrivial $\left(f_T,w_T\right)$-weighted tree $T$ and $f_T\left(T\right)$

Output: $F_T={\left\{\left(f_T\left(T_u^v\right),f_T\left(T_v^u\right)\right)\right\}}_{uv\in E\left(T\right)}$

Initiate with $S=\left\{a\in V\left(T\right) |\mathrm{deg}\left(a\right)=1\right\}$

$while \left(E\left(T\right)\ne \varphi \right)$

$Leaves\leftarrow S$

$S=\varphi$

$for v\in leaves$

$u\leftarrow N\left(v\right)$

($f_T\left(T_u^v\right),f_T\left(T_v^u\right)) \leftarrow \left(f_T\left(T\right)-f_T\left(v\right), f_T\left(v\right)\right)$

$f_T\left(u\right)+=f_T\left(v\right)$

$if\mathrm{deg}\left(u\right)-1=1.$ #Will be a leaf

$S=S\cup \left\{u\right\}$

$T=T-\left\{v\right\}$    #Remove $v$ from adj list

Corollary 1.

For an $n$-vertex tree $T$, the sets, $N_T$ and, $F_T$ can be computed in $O\left(n\right)$.

Corollary 2.

Let $T$ be a $\left(f_T, w_T\right)$-weighted tree with $n$ vertices and $g_T=\alpha {\sigma }_T+\beta h_T$ for some, $\alpha ,\beta \in ℝ$. One can compute and sort $\left\{g_T^{\prime }\left(\overrightarrow{ax}\right)\right| x\in N_T\left(a\right)\}$ for all $a\in V\left(G\right)$ with the time complexity of $O\left(\sum _{v\in V\left(T\right)}deg\left(v\right)log\mathrm{deg}\left(v\right)\right)$, that is on average $O\left(n\right)$.

The following result gives us an important fact about the weighted trees.

Lemma 2.

Suppose $P=v_1{v}_2\dots v_n$, $n>2$, is a path in a $\left(f_T,w_T\right)$-weighted tree $T$. If $w_T>0$ and ${\sigma }_T^{\prime }\left(\overrightarrow{v_1{v}_2}\right)\ge 0$, then $v_2\dots v_n$ is, ${\sigma }_T$-increasing. If $f_T>0$, $w_T>0$, and $h_T^{\prime }\left(\overrightarrow{v_1{v}_2}\right)\ge 0$, then $v_2\dots v_{n+1}$ is, $h_T$-increasing. If $g_T=\alpha {\sigma }_T+\beta h_T$, (for $\alpha ,\beta \in {ℝ}^{\ge 0}, \alpha +\beta \ne 0)$ $f_T>0$, $w_T>0$, and $g_T^{\prime }\left(\overrightarrow{v_1{v}_2}\right)\ge 0$, then $v_2\dots v_n$ is, $g_T$-increasing.

Proof. 

Assume $T$ is a $\left(f_T,w_T\right)$-weighted tree and $xyz$ is a path in $T$. Without loss of generality, we can prove the lemma for $xyz$. We know that $V\left(T_u^v\right)\cup V\left(T_v^u\right)=V\left(T\right)$ and $V\left(T_u^v\right){\displaystyle \cap }V\left(T_v^u\right)=\varnothing$ for any $uv\in E\left(T\right)$. Thus, for some $A\subset V\left(T\right)$,

$$V\left(T_y^z\right)=V\left(T_x^y\right){\displaystyle \cup }\left\{y\right\}{\displaystyle \cup }A,$$

(6)

and

$$V\left(T_z^y\right)=V\left(T_y^x\right)-\left\{y\right\}-A.$$

(7)

Therefore,

$$V\left(T_x^y\right)\subset V\left(T_y^z\right) \mathrm{and} V\left(T_y^x\right)\supset V\left(T_z^y\right)$$

(8)

We use Equations (2) and (5) for computing ${\sigma }_T^{\prime }$ and $h_T^{\prime }$. Then by the assumption ${\sigma }_T^{\prime }\left(\overrightarrow{xy}\right)=n_T\left(T_x^y\right)-n_T\left(T_y^x\right)\ge 0$. Thus by Equation (8) ${\sigma }_T^{\prime }\left(\overrightarrow{yz}\right)=n_T\left(T_y^z\right)-n_T\left(T_z^y\right)>0$. Since $w_T>0$, $w\left(yz\right){\sigma }_T^{\prime }\left(\overrightarrow{yz}\right)>0$. That is, ${\sigma }_T\left(z\right)>{\sigma }_T\left(y\right)$ which completes the proof for ${\sigma }_T$ case. Similarly, assume $h_T^{\prime }\left(\overrightarrow{xy}\right)=f_T\left(T_x^y\right)-f_T\left(T_y^x\right)\ge 0$. If $f_T>0$, by Equation (8) $h_T^{\prime }\left(\overrightarrow{yz}\right)=f_T\left(T_y^z\right)-f_T\left(T_z^y\right)>0$. If, in addition $w_T>0$, then $w\left(yz\right)h_T^{\prime }\left(\overrightarrow{yz}\right)>0$. Thus, by Definition 2, $h_T\left(z\right)>h_T\left(y\right)$. That completes the proof for $h_T$ case. The proof for the $g_T^{\prime }$ case is like $h_T^{\prime }$ case. This completes the proof. □

Using Lemma 2, we attained the following result regarding the convexity of a tree.

Theorem 1.

Any positively edge-weighted tree is $\sigma$-convex, and any positively weighted tree is ($\alpha \sigma +\beta h)$-convex, for $\alpha ,\beta \in {ℝ}^{\ge 0}$.

Proof. 

Let us have a positively edge-weighted tree with at least three vertices. Assume a vertex, $v_1$, is not a $\sigma$-Root and $v_1{v}_2\dots v_n$ is the shortest possible path (in terms of the number of edges) between $v_1$ and a $\sigma$-Root, $v_n$. Assume toward a contradiction that $v_1{v}_2\dots v_n$ is not decreasing. Thus, suppose $v_i{v}_{i+1}$ is the first edge from $v_1$ toward $v_n$, such that $\sigma \left(v_i\right)\le \sigma \left(v_{i+1}\right)$. Since the edge weights are positive, ${\sigma }^{\prime }\left(\overrightarrow{v_i{v}_{i+1}}\right)\ge 0$. Then, by Lemma 2, the path $v_{i+1}{v}_{i+2}\dots v_n$ is increasing. That is, $\sigma \left(v_i\right)\le \sigma \left(v_n\right)$ and $i<n$. If $\sigma \left(v_i\right)=\sigma \left(v_n\right)$, $v_i$ also is a $\sigma$-Root and $v_1{v}_2\dots v_i$ is shorter than $v_1{v}_2\dots v_n$ while having the same specification, which is a contradiction with $v_1{v}_2\dots v_n$ being the shortest. And if, $\sigma \left(v_i\right)<\sigma \left(v_n\right)$, contradicts with, $v_n$ being a $\sigma$-Root. Therefore, $v_1{v}_2\dots v_n$ is decreasing. Since $v_1$ was arbitrary, the tree is $\sigma$-convex. For the proof of $\alpha \sigma +\beta h$ case, use the same strategy as for $\sigma$, along with the positivity of the vertices’ weight. □

Corollary 3.

Assume that $g=\alpha \sigma +\beta h$, $\alpha ,\beta \in {ℝ}^{\ge 0}, \alpha +\beta \ne 0$. Then, a positively weighted tree has at most two $g$-Roots. If $x$ and $y$ are two $g$-Roots of a tree, then they are adjacent, and $g^{\prime }\left(\overrightarrow{xy}\right)=g^{\prime }\left(\overrightarrow{yx}\right)=0$. Moreover, if $c$ is a tree’s $g$-Root and $v$ is a non-Root neighbor of $c$, then $g^{\prime }\left(\overrightarrow{cv}\right)>0$, and $g^{\prime }\left(\overrightarrow{vc}\right)<0$. Usefully, if $P=v_1{v}_2\dots v_m$ is a decreasing path between $v_1$ and a $g$-Root, $v_m$, then $g\prime \left(\overrightarrow{v_{i}a}\right)<0$ if and only if $a=v_{i+1}$, $i<m$. In addition, $P$ is the longest $g$-decreasing path starting from $v_1$. Finally, a leaf is not a $\left(\alpha \sigma +\beta h\right)$-Root of a positively weighted tree with more than 2 vertices.

Definition 4.

Suppose $G$ is a $\left(f_G,w_G\right)$-weighted graph. Regarding $f_G^{\prime }$ and $d_G$, we define and denote the discrete integral of $f_G^{\prime }$ along a path, $P=v_1{v}_2\dots v_n$ from $v_1$ to $v_n$ as follows:

$${{\displaystyle \int }}_P{f}_G^{\prime }{d}_G={{\displaystyle \sum }}_{i=1}^{n-1}{f}_G^{\prime }\left(\overrightarrow{v_i{v}_{i+1}}\right).d_G\left(v_i,v_{i+1}\right).$$

If $a,b\in V\left(G\right)$ and $P_G\left(a,b\right)$ is an arbitrary path between $a$ and $b,$ we denote ${\int }_{P_G\left(a,b\right)}{f}_G^{\prime }{d}_G$ by

$${{\displaystyle \int }}_a^b{f}_G^{\prime }{d}_G$$

By Definitions 2 and 4, we have:

Theorem 2.

Suppose $G$ is a connected $\left(f_G,w_G\right)$-weighted graph and $a,b\in V\left(G\right)$. If $f_G^{\prime }$ is consistent, then for any path from $a$ to $b$,

$${{\displaystyle \int }}_a^b{f}_G^{\prime }{d}_G=f_G\left(b\right)-f_G\left(a\right).$$

Using Figure 1 as graph $G$ with the given weights and the above result or Definition 2.12, one can see that,

$$\begin{array}{c}{{\displaystyle \int }}_x^y{f}_G^{\prime }{d}_G={{\displaystyle \int }}_{P=xay}^{ }{f}_G^{\prime }{d}_G={{\displaystyle \int }}_{P=xaby}^{ }{f}_G^{\prime }{d}_G={{\displaystyle \int }}_{P=xacby}^{ }{f}_G^{\prime }{d}_G={{\displaystyle \int }}_{P=xcby}^{ }{f}_G^{\prime }{d}_G\\ ={{\displaystyle \int }}_{P=xcay}^{ }{f}_G^{\prime }{d}_G={{\displaystyle \int }}_{P=xcaby}^{ }{f}_G^{\prime }{d}_G=-2.\end{array}$$

3. Some Applications of Discrete Integral and Derivative and Convexity

In this section, we formally define three optimization problems on trees. As an application of the results of the previous section, we will have efficient solutions to the problems with some possible comparisons with existing solutions at the end. The compared problems are not clearly defined in the same way we do. We try to convert them for some partial comparison.

The routing cost of $G$ for a given set of sources $S\subseteq V\left(G\right)$ and the total distance of $G$ are defined as follows, respectively:

$$RC\left(G,S\right)={{\displaystyle \sum }}_{v\in V\left(G\right)}{{\displaystyle \sum }}_{s\in S}{d}_G\left(v,s\right), D\left(G\right)=\frac{1}{2}{{\displaystyle \sum }}_{v\in V\left(G\right)}{{\displaystyle \sum }}_{v\in V\left(G\right)}{d}_G\left(v,s\right).$$

The Wiener index, $W\left(G\right)$, of a simple graph $G$, $(f_G=1,w_G=1)$ is equal to its total distance [23,24]. By setting $\alpha ,\beta ,$ $w_G$, and $f_G$; $W_{\alpha ,\beta }$, defined in the introduction, can produce any of $D$, $W$, $W_{+}$, $W_{\times }$, or $RC$ for a graph, $G$. So, $W_{\alpha ,\beta }$ generalizes all the mentioned graph invariants.

Definition 5.

Let $T$ be a weighted tree and $T_{ϵ\backslash e}=T-e+ϵ$, where $e\in E\left(T\right)$ and $ϵ\in E\left(T^c\right)$.

• We say  $ϵ\in E\left(T^c\right)$  is a switch of  $e\in E\left(T\right)$, if  $T_{ϵ\backslash e}$  is a tree. Then  $T_{ϵ\backslash e}$  is called a switch.
• We say $ϵ\in E\left(T^c\right)$ is a BS of $e\in E\left(T\right)$ w.r.t. $W_{\alpha ,\beta }$ if $W_{\alpha ,\beta }\left(T_{ϵ\backslash e}\right)$ is minimum, i.e., $W_{\alpha ,\beta }\left(T_{ϵ\backslash e}\right)=\underset{s\in E\left(T^c\right) }{\mathit{min}}{W}_{\alpha ,\beta }\left(T_{s\backslash e}\right).$
• The coordinate of $T$ is shown and defined with $Q_T=\left\{F_T,N_T,W_{\times }\left(T\right),W_{+}\left(T\right)\right\}$.

Based on the BS definition, we define three problems. The second and third problems are created merely for comparison. Assume $T$ is a weighted tree with $E\left(T\right)={\left\{e_i\right\}}_{i=1}^n$ and we have coordinated, $Q_T$.

Problem1: Input: 1. $T$, 2. $Q_T$, 3.  $e\in E\left(T\right)$, 4.  $w,\alpha ,\beta \in {ℝ}^{\ge 0}$. Output: 1.  $ϵ\in E\left(T^c\right)$, where $ϵ$ is a BS of $e$ w.r.t. $W_{\alpha ,\beta }$ with $w_{T_{ϵ\backslash e}}\left(ϵ\right)=w$. 2.  $W_{\alpha ,\beta }\left(T_{ϵ\backslash e}\right)$, 3.  $T_{ϵ\backslash e}$, 4.  $Q_{T_{ϵ\backslash e}}$.

Problem2: Input: 1. $T$ with $E\left(T\right)={\left\{e_i\right\}}_{i=1}^n$ 2. $Q_T$, 3. ${\left\{w_i,{\alpha }_i,{\beta }_i\in {ℝ}^{\ge 0}\right\}}_{i=1}^n$. Output: 1. $r$, 2. ${ϵ}_r\in E\left(T^c\right)$, 3. $T_{{ϵ}_r\backslash e_r}$, 4. $Q_{T_{{ϵ}_r\backslash e_r}}$, 5. $W_{{\alpha }_r,{\beta }_r}\left(T_{{ϵ}_r\backslash e_r}\right)$, where $W_{{\alpha }_r,{\beta }_r}\left(T_{{ϵ}_r\backslash e_r}\right)=min{\left\{W_{{\alpha }_i,{\beta }_i}\left(T_{{ϵ}_i\backslash e_i}\right)\right\}}_{i=1}^n$ and ${ϵ}_i$ is a BS of $e_i$ w.r.t. $W_{{\alpha }_i,{\beta }_i}$ with $w_i=w_{T_{{ϵ}_i\backslash e_i}}\left({ϵ}_i\right)$. (Overall best switch).

Problem3: Input: 1. $T$ with $E\left(T\right)={\left\{e_i\right\}}_{i=1}^n$, 2. $Q_T$, 3. ${\left\{w_i,{\alpha }_i,{\beta }_i\in {ℝ}^{\ge 0}\right\}}_{i=1}^n$. Output: 1. ${\left\{\left({ϵ}_i\in E\left(T^c\right),W_{{\alpha }_i,{\beta }_i}\left(T_{{ϵ}_i\backslash e_i}\right)\right)\right\}}_{i=1}^n$, where ${ϵ}_i$ is a BS of $e_i$ w.r.t. $W_{{\alpha }_i,{\beta }_i}$ with $w_i=w_{T_{{ϵ}_i\backslash e_i}}\left({ϵ}_i\right)$. (All best switches).

Definition 6.

For a numerical graph invariant, $W_{*}$, and a switch $T_{s\backslash t }$ let

$$W_{*}^{\prime }\left(T_{s\backslash t }\right)=W_{*}\left(T_{s\backslash t }\right)-W_{*}\left(T\right).$$

Lemma 3.

Let $T$ be a $(f_T,w_T)$-weighted tree, $xy\in E\left(T\right)$, and $g_T=\alpha {\sigma }_T+\beta h_T$ for some $\alpha ,\beta \in ℝ$. Using, $F_T$ and $N_T$, we can calculate $g_{T_x^y}^{\prime }$ on the path from $x$ toward any vertex of $T_x^y$. A similar argument holds for a path from $y$ toward any vertex of $T_y^x$.

Proof. 

Let $T$ be a $\left(f_T,w_T\right)$-weighted tree and $xy\in E\left(T\right)$ with $T-\left\{xy\right\}=T_x^y{\displaystyle \cup }{T}_y^x$ and $g_T=\alpha {\sigma }_T+\beta h_T$, $\alpha ,\beta \in ℝ$. Assume $v_1{v}_2\dots v_n$ is a path in $T_x^y$, with $v_1=x$. Using Equations (1), (2), (5), and $\left\{N_T ,F_T\right\}={\left\{\left(n_T\left(T_u^v\right),n_T\left(T_v^u\right)\right),\left(f_T\left(T_u^v\right),f_T\left(T_v^u\right)\right)\right\}}_{uv\in E\left(T\right)}$ we could extract, ${\sigma }_T^{\prime }$ and $h_T^{\prime }$, and so $g_T^{\prime }=\alpha {\sigma }_T^{\prime }+\beta h_T^{\prime }$ on $v_1{v}_2\dots v_n$. However, we need to get $g_{T_x^y}^{\prime }$ through $v_1{v}_2\dots v_n$. To do so, one can check for $v_1{v}_2\dots v_n,$ 

$$(n_{T_x^y}(\left[T_x^y{]}_{v_i}^{v_{i+1}}\right), n_{T_x^y}\left(\left[T_x^y{]}_{v_{i+1}}^{v_i}\right)\right)=\left(n_T\left(T_{v_i}^{v_{i+1}}\right)-n_T\left(T_y^x\right), n_T\left(T_{v_{i+1}}^{v_i}\right)\right), 0<i<n,$$

(9)

$$(f_{T_x^y}(\left[T_x^y{]}_{v_i}^{v_{i+1}}\right), f_{T_x^y}\left(\left[T_x^y{]}_{v_{i+1}}^{v_i}\right)\right)=\left(f_T\left(T_{v_i}^{v_{i+1}}\right)-f_T\left(T_y^x\right), f_T\left(T_{v_{i+1}}^{v_i}\right)\right). 0<i<n.$$

(10)

Thus, using Equations (1), (2) and (5), along with (9) and (10):

$${\sigma }_{T_x^y}^{\prime }\left(\overrightarrow{v_i{v}_{i+1}}\right)={\sigma }_T^{\prime }\left(\overrightarrow{v_i{v}_{i+1}}\right)-n_T\left(T_y^x\right), h_{T_x^y}^{\prime }\left(\overrightarrow{v_i{v}_{i+1}}\right)=h_T^{\prime }\left(\overrightarrow{v_i{v}_{i+1}}\right)-f_T\left(T_y^x\right).$$

That is, using $F_T$ and $N_T$, we can compute $g_{T_y^x}^{\prime }\left(\overrightarrow{v_i{v}_{i+1}}\right)$ as follows:

$$g_{T_x^y}^{\prime }\left(\overrightarrow{v_i{v}_{i+1}}\right)=\alpha {\sigma }_T^{\prime }\left(\overrightarrow{v_i{v}_{i+1}}\right)+\beta h_T^{\prime }\left(\overrightarrow{v_i{v}_{i+1}}\right)-\alpha n_T\left(T_y^x\right)-\beta f_T\left(T_y^x\right).$$

Symmetrically, the argument holds for the $T_y^x$ and $y$ case. □

It is straightforward but involves some long computation to find out the following.

Lemma 4.

Suppose $T$ is a $\left(f_T,w_T\right)$-weighted tree with $uv\in E\left(T\right)$ and $xy\in E\left(T^c\right)$. If $x\in V\left(T_u^v\right)$ and $y\in V\left(T_v^u\right)$, then

$$W_{\alpha ,\beta }^{\prime }\left(T_{xy\backslash uv}\right)={{\displaystyle \int }}_u^x{p}^{\prime }{d}_{T_u^v}+{{\displaystyle \int }}_v^y{q}^{\prime }{d}_{T_v^u}+F{N}_{\alpha ,\beta }\left(uv\right)\left[w_{T_{xy\backslash uv}}\left(xy\right)-w_T\left(uv\right)\right],$$

where,

$$F{N}_{\alpha ,\beta }\left(uv\right)=\left[\alpha f_T\left(T_u^v\right)f_T\left(T_v^u\right)+\beta \left(n_T\left(T_u^v\right)f_T\left(T_v^u\right)+f_T\left(T_u^v\right)n_T\left(T_v^u\right)\right)\right],\alpha ,\beta \in R$$

and

$$p\left(a\right)=\left[\alpha f_T\left(T_v^u\right)+\beta n_T\left(T_v^u\right)\right]h_{T_u^v}\left(a\right)+\beta f_T\left(T_v^u\right){\sigma }_{T_u^v}\left(a\right),\hspace{1em}\hspace{1em}\hspace{1em}a\in V\left(T_u^v\right),$$

$$q\left(b\right)=\left[\alpha f_T\left(T_u^v\right)+\beta n_T\left(T_u^v\right)\right]h_{T_v^u}\left(b\right)+\beta f_T\left(T_u^v\right){\sigma }_{T_v^u}\left(b\right),\hspace{1em}\hspace{1em}\hspace{1em}b\in V\left(T_v^u\right).$$

Proof. 

Assume $T$ is a tree. If we remove $uv\in E\left(T\right)$ and connect, $T_u^v$ and $T_v^u$ with $xy\in E\left(T^c\right),$ where $x\in V\left(T_u^v\right)$ and $y\in V\left(T_v^u\right)$, then

$$\begin{array}{ll}{W}_{\alpha ,\beta }\left(T_{xy\backslash uv}\right)& =W_{\alpha ,\beta }\left(T_u^v\right)+W_{\alpha ,\beta }\left(T_v^u\right)\\ & +{\displaystyle \sum _{a\in V\left(T_u^v\right)}}{\displaystyle \sum _{b\in V\left(T_v^u\right)}}\left[\alpha f_T\left(a\right)f_T\left(b\right)+\beta \left(f_T\left(a\right)+f_T\left(b\right)\right)\right].[d_T\left(x,a\right)\\ & +w_{T_{xy\backslash uv}}\left(xy\right)+d_T\left(b,y\right)]\end{array}$$

$$\begin{array}{ll}=W_{\alpha ,\beta }\left(T_u^v\right)& +W_{\alpha ,\beta }\left(T_v^u\right)+\left[\alpha f_T\left(T_v^u\right)+\beta n_T\left(T_v^u\right)\right]h_{T_u^v}\left(x\right)+\left[\alpha f_T\left(T_u^v\right)+\beta n_T\left(T_u^v\right)\right]h_{T_v^u}\left(y\right)\\ & +\beta [f_T\left(T_v^u\right){\sigma }_{T_u^v}\left(x\right)+f_T\left(T_u^v\right){\sigma }_{T_v^u}\left(y\right)\\ & +w_{T_{xy\backslash uv}}\left(xy\right)[\alpha f_T\left(T_u^v\right)f_T\left(T_v^u\right)\\ & +\beta \left(n_T\left(T_u^v\right)f_T\left(T_v^u\right)+f_T\left(T_v^u\right)f_T\left(T_u^v\right)\right)]\end{array}$$

(11)

Using the fact that $W_{\times }\left(T_{uv\backslash uv}\right)=W_{\times }\left(T\right)$ and the above formula,

$$\begin{array}{ll}{W}_{\alpha ,\beta }^{\prime }\left(T_{xy\backslash uv}\right)& =W_{\alpha ,\beta }\left(T_{xy\backslash uv}\right)-W_{\alpha ,\beta }\left(T\right)\\ & =\left[p\left(x\right)-p\left(u\right)\right]+\left[q\left(y\right)-q\left(v\right)\right]+F{N}_{\alpha ,\beta }\left(uv\right)[w_{T_{xy\backslash uv}}\left(xy\right)\\ & -w_T\left(uv\right)].\end{array}$$

where $F{N}_{\alpha ,\beta }\left(uv\right)=\left[\alpha f_T\left(T_u^v\right)f_T\left(T_v^u\right)+\beta \left(n_T\left(T_u^v\right)f_T\left(T_v^u\right)+f_T\left(T_u^v\right)n_T\left(T_v^u\right)\right)\right]$ and

$$p\left(a\right)=\left[\alpha f_T\left(T_v^u\right)+\beta n_T\left(T_v^u\right)\right]h_{T_u^v}\left(a\right)+\beta f_T\left(T_v^u\right){\sigma }_{T_u^v}\left(a\right),\hspace{1em}\hspace{1em}\hspace{1em}a\in V\left(T_u^v\right),$$

$$q\left(b\right)=\left[\alpha f_T\left(T_u^v\right)+\beta n_T\left(T_u^v\right)\right]h_{T_v^u}\left(b\right)+\beta f_T\left(T_u^v\right){\sigma }_{T_v^u}\left(b\right),\hspace{1em}\hspace{1em}\hspace{1em}b\in V\left(T_v^u\right).$$

Since $T_u^v$ and $T_v^u$ are connected, and $p$ and $q$ are consistent; by Lemma 1 and Theorem 2, we have:

$$W_{\alpha ,\beta }^{\prime }\left(T_{xy\backslash uv}\right)={\int }_u^x{p}^{\prime }{d}_{T_u^v}+{\int }_v^y{q}^{\prime }{d}_{T_v^u}+F{N}_{\alpha ,\beta }\left(uv\right)\left[w_{T_{xy\backslash uv}}\left(xy\right)-w_T\left(uv\right)\right].\square$$

The above lemma gives a clue between a BS of $uv\in V\left(T\right)$ w.r.t $W_{\alpha ,\beta }$ and the $p$-Roots and $q$-Roots of $T_u^v$ and $T_v^u$. Often, finding a BS is equivalent to finding some Roots.

Lemma 5.

Suppose $T$ is a positively weighted tree with at least three vertices and $uv\in E\left(T\right)$. If $a$ and $b$ are a $p$-Root of $T_u^v$ and a $q$-Root of $T_v^u$, respectively, then a BS of $uv$ w.r.t $W_{\alpha ,\beta }$ is $xy$ with $x\in N_T\left(a\right){\displaystyle \cup }\left\{a\right\}$ and $y\in N_T\left(b\right){\displaystyle \cup }\left\{b\right\}$. More precisely, let the following be vertex weight functions for the relevant vertices:

$$p\left(c\right)=\left[\alpha f_T\left(T_v^u\right)+\beta n_T\left(T_v^u\right)\right]h_{T_u^v}\left(c\right)+\beta f_T\left(T_v^u\right){\sigma }_{T_u^v}\left(c\right),\hspace{1em}\hspace{1em}\hspace{1em}c\in V\left(T_u^v\right),$$

$$q\left(c\right)=\left[\alpha f_T\left(T_u^v\right)+\beta n_T\left(T_u^v\right)\right]h_{T_v^u}\left(c\right)+\beta f_T\left(T_u^v\right){\sigma }_{T_v^u}\left(c\right),\hspace{1em}\hspace{1em}\hspace{1em}c\in V\left(T_v^u\right).$$

Then a choice of $xy$ as a BS of $uv$ w.r.t $W_{\alpha ,\beta }$ is as follows:

A 

If $\left(u,v\right)=(p$-Root of $T_u^v$, $q$-Root of  $T_v^u)$,

• $\left(x,y\right)=\left(u,z\right)$ where $q\left(z\right)=\underset{c\in N_{T_v^u}\left(v\right)}{min}q\left(c\right)$, or
• $\left(x,y\right)=\left(z,v\right)$ where $p\left(z\right)=\underset{c\in N_{T_u^v}\left(u\right)}{min}p\left(c\right)$.

If $q^{\prime }\left(\overrightarrow{vz}\right)w_T\left(vz\right)<p^{\prime }\left(\overrightarrow{uz}\right)w_T\left(uz\right)$, 1 gives a choice for $xy$; otherwise, $2$.

B 

If $\left(u,v\right)\ne (p$-Root of $T_u^v$, $q$-Root of  $T_v^u)$, then $\left(x,y\right)=(p$-Root of $T_u^v$, $q$-Root of  $T_v^u)$.

Moreover, $F_T=F_T{}_{xy\backslash uv}$ and $N_T=N_T{}_{xy\backslash uv}$ except for the edges on $P_T\left(u,x\right)$ and $P_T\left(v,y\right)$. More precisely, if $P_{T_u^v}\left(u,x\right)=u_1{u}_2\dots u_m$ is the path between $u=u_1$ and $x=u_m$,

$$\left(n_{T_{xy\backslash uv}}\left(T_{u_i}^{u_{i+1}}\right), n_{T_{xy\backslash uv}}(T_{u_{i+1}}^{u_i}\right))=\left(n_T\left(T_{u_i}^{u_{i+1}}\right)-n_T\left(T_v^u\right),\hspace{1em}\hspace{1em}\hspace{1em}{n}_T(T_{u_{i+1}}^{u_i}\right)+n_T\left(T_v^u\right)),$$

$$\left(f_{T_{xy\backslash uv}}\left(T_{u_i}^{u_{i+1}}\right), f_{T_{xy\backslash uv}}(T_{u_{i+1}}^{u_i}\right))=\left(f_T\left(T_{u_i}^{u_{i+1}}\right)-f_T\left(T_v^u\right), f_T(T_{u_{i+1}}^{u_i}\right)+f_T\left(T_v^u\right),0<i<m.$$

And, if $P_{T_v^u}\left(v,y\right)=v_1{v}_2\dots v_n$ is a path between $v=v_1$ and $y=v_n$,

$$\left(n_{T_{xy\backslash uv}}\left(T_{v_i}^{v_{i+1}}\right), n_{T_{xy\backslash uv}}(T_{v_{i+1}}^{v_i}\right))=\left(n_T\left(T_{v_i}^{v_{i+1}}\right)-n_T\left(T_u^v\right),\hspace{1em}\hspace{1em}\hspace{1em}{n}_T(T_{v_{i+1}}^{v_i}\right)+n_T\left(T_u^v\right)),$$

$$\left(f_{T_{xy\backslash uv}}\left(T_{v_i}^{v_{i+1}}\right), f_{T_{xy\backslash uv}}(T_{v_{i+1}}^{v_i}\right))=\left(f_T\left(T_{v_i}^{v_{i+1}}\right)-f_T\left(T_u^v\right), f_T(T_{v_{i+1}}^{v_i}\right)+f_T\left(T_u^v\right)),0<i<n.$$

Proof. 

Assume we have the lemma assumptions. By Equation (11),

$$W_{\alpha ,\beta }\left(T_{st\backslash uv}\right)=p\left(s\right)+q\left(t\right)+r,\hspace{1em}\hspace{1em}\hspace{1em}s\in V\left(T_u^v\right) \mathrm{and} t\in V\left(T_v^u\right)$$

(12)

where $r$ is independent of the choice of s and $t$. And the values of $p\left(s\right)$ and $q\left(t\right)$ are independent of each other. By definition, if $a\in V\left(T_u^v\right)$ and $b\in V\left(T_v^u\right)$ minimize Equation (12) and $ab\ne uv,$ then $ab$ is a BS of $uv$. One sees that by minimizing Equation (12) inclusively, we do not exclude $uv$ as a choice for $ab$, since:

$$\underset{s\in V\left(T_u^v\right) }{min}p\left(s\right)+\underset{t\in V\left(T_v^u\right) }{min}q\left(t\right)+r=\underset{st\in E\left(T^c\right){\displaystyle \cup }\left\{uv\right\} }{\mathit{min}}{W}_{\alpha ,\beta }\left(T_{st\backslash uv}\right).$$

(13)

Accordingly, $\left(a,b\right)$ minimizes Equation (12) if and only if $\left(p\left(a\right),q\left(b\right)\right)=\left(\underset{s\in V\left(T_u^v\right)}{min}p\left(s\right), \underset{t\in V\left(T_v^u\right)}{min}q\left(t\right)\right)$. That is, $\left(a,b\right)=(p$-Root of $T_u^v$, $q$-Root of $T_v^u)$.

If case A happens, which is $\left(u,v\right)=(p$-Root of $T_u^v$, $q$-Root of $T_v^u)$ and also $\left(x,y\right)=(p$-Root of $T_u^v$, $q$-Root of $T_v^u)$, then we might have $xy=uv$. To exclude $uv$ in the minimization of Equation (12), we avoid the case that $u$ and $v$ appear concurrently by letting $\left(p\left(x\right),q\left(y\right)\right)$ is equal to either $\left(\underset{s\in V\left(T_u^v\right)\backslash u }{min}p\left(s\right), \underset{t\in V\left(T_v^u\right) }{min}q\left(t\right)\right)$ or $\left(\underset{s\in V\left(T_u^v\right) }{min}p\left(s\right), \underset{t\in V\left(T_v^u\right) \backslash v }{min}q\left(t\right)\right)$. By Theorem 1 and the assumptions $T_u^v$ and $T_v^u$ are convex. That is,

$$\underset{s\in V\left(T_u^v\right)\backslash u }{min}p\left(s\right)=\underset{s\in N_{T_u^v}\left(u\right) }{min}p\left(s\right) \mathrm{and} \underset{t\in V\left(T_v^u\right)\backslash v }{min}q\left(t\right)=\underset{t\in N_{T_v^u}\left(v\right) }{min}q\left(t\right)$$

As a result, either

$$1-\left(x,y\right)=\left(u, z\right) \mathrm{where} q\left(z\right)=\underset{b\in N_{T_u^v}\left(u\right) }{min}q\left(b\right)$$

$$2-\left(x,y\right)=\left(z, v\right) \mathrm{where} p\left(z\right)=\underset{a\in N_{T_u^v}\left(u\right) }{min}p\left(a\right)$$

Per Lemma 4, in case 1—,$W_{\alpha ,\beta }^{\prime }\left(T_{xy\backslash uv}\right)-r={\int }_u^{u=x}{p}^{\prime }{d}_{T_u^v}+{\int }_v^y{q}^{\prime }{d}_{T_v^u}={\int }_v^y{q}^{\prime }{d}_{T_v^u}=q^{\prime }\left(\overrightarrow{vz}\right)w_T\left(vz\right)$ and in case 2—$W_{\alpha ,\beta }^{\prime }\left(T_{xy\backslash uv}\right)-r=p^{\prime }\left(\overrightarrow{uz}\right)w_T\left(uz\right)$. Thus, if $p^{\prime }\left(\overrightarrow{uz}\right)w_T\left(uz\right)>q^{\prime }\left(\overrightarrow{vz}\right)w_T\left(vz\right)$, then 1 gives the choice of $\left(x,y\right)$. If $p^{\prime }\left(\overrightarrow{uz}\right)w_T\left(uz\right)<q^{\prime }\left(\overrightarrow{vz}\right)w_T\left(vz\right)$, then $\left(x,y\right)$ comes from 2. Otherwise, either 1 or 2 is the choice.

Now assume $\left(u,v\right)\ne (p$-Root of $T_u^v$, $q$-Root of $T_v^u)$. If $\left(a,b\right)=(p$-Root of $T_u^v$, $q$-Root of $T_v^u)$, then $\left(u,v\right)\ne \left(a,b\right)$. Moreover, $\left(a,b\right)$ minimizes $W_{\alpha ,\beta }$ in Equation (12). So $\left(x,y\right)=\left(a,b\right)$ is the right choice. This completes the proof of B.

To form $T_{xy\backslash uv}$ we remove $uv\in E\left(T\right)$ and reconnect the components of $T-u$ using $x\in V\left(T_u^v\right)$ and $y\in V\left(T_v^u\right)$, $uv\ne xy$. Thus, $F_T\ne F_T{}_{xy\backslash uv}$ and $N_T\ne N_T{}_{xy\backslash uv}$ in general. Precisely, $\left(n_T\left(T_a^b\right),n_T\left(T_b^a\right)\right)\ne \left(n_{T_{xy\backslash uv}}\left(T_a^b\right),n_{T_{xy\backslash uv}}\left(T_b^a\right)\right)$ or $\left(f_T\left(T_a^b\right),f_T\left(T_b^a\right)\right)\ne \left(f_{T_{xy\backslash uv}}\left(T_a^b\right),f_{T_{xy\backslash uv}}\left(T_b^a\right)\right)$ happens if $ab\in P_T\left(u,x\right)$ or $ab\in P_T\left(v,y\right)$. By Definition 1 $f_T\left(T_a^b\right)+f_T\left(T_b^a\right)=f_T\left(T\right)$ and $n_T\left(T_a^b\right)+n_T\left(T_b^a\right)=\left|V\left(T\right)\right|$. And, by Lemma 3 Equations (9) and (10), if $P_{T_u^v}\left(u,x\right)=u_1{u}_2\dots u_m$ is the path between $u=u_1$ and $x=u_m$,

$$\left(n_{T_{xy\backslash uv}}\left(T_{u_i}^{u_{i+1}}\right), n_{T_{xy\backslash uv}}(T_{u_{i+1}}^{u_i}\right))=\left(n_T\left(T_{u_i}^{u_{i+1}}\right)-n_T\left(T_v^u\right), n_T(T_{u_{i+1}}^{u_i}\right)+n_T\left(T_v^u\right)),$$

$$\left(f_{T_{xy\backslash uv}}\left(T_{u_i}^{u_{i+1}}\right), f_{T_{xy\backslash uv}}(T_{u_{i+1}}^{u_i}\right))=\left(f_T\left(T_{u_i}^{u_{i+1}}\right)-f_T\left(T_v^u\right), f_T(T_{u_{i+1}}^{u_i}\right)+f_T\left(T_v^u\right)),0<i<m.$$

And symmetrically, for $P_{T_v^u}\left(v,y\right)=v_1{v}_2\dots v_n$ with $v=v_1$ and $y=v_n$,

$$\left(n_{T_{xy\backslash uv}}\left(T_{v_i}^{v_{i+1}}\right), n_{T_{xy\backslash uv}}(T_{v_{i+1}}^{v_i}\right))=\left(n_T\left(T_{v_i}^{v_{i+1}}\right)-n_T\left(T_u^v\right), n_T(T_{v_{i+1}}^{v_i}\right)+n_T\left(T_u^v\right)),$$

$$\left(f_{T_{xy\backslash uv}}\left(T_{v_i}^{v_{i+1}}\right), f_{T_{xy\backslash uv}}(T_{v_{i+1}}^{v_i}\right))=\left(f_T\left(T_{v_i}^{v_{i+1}}\right)-f_T\left(T_u^v\right), f_T(T_{v_{i+1}}^{v_i}\right)+f_T\left(T_u^v\right)), 0<i<n.$$

□

Lemma 6.

For a $\left(f_T,w_T\right)$-weighted tree $T$,

$$W_{\times }\left(T\right)={\displaystyle \sum }_{uv\in E\left(T\right)}[f_T\left(T_u^v\right)f_T\left(T_v^u\right)]w_T\left(uv\right),$$

and,

$$W_{+}\left(T\right)={\displaystyle \sum }_{uv\in E\left(T\right)}[n_T\left(T_u^v\right)f_T\left(T_v^u\right)+n_T\left(T_v^u\right)f_T\left(T_u^v\right)]w_T\left(uv\right).$$

Proof. 

We prove the first equation using the double-counting principle. Assume $T^{\prime }$ is a copy of $T$ with the edge weights set to 0 at the start. Let $u,v\in V\left(T\right)$ and $P_T\left(u,v\right)$ is the path between $u$ and $v$. For every $ab\in P_T\left(u,v\right)$ add the number $w\left(uv\right)f_T\left(a\right)f_T\left(b\right)$ to the corresponding edge of $ab$ in $T^{\prime }$. Then $\sum _{uv\in P_T\left(u,v\right)}{w}_{T^{\prime }}\left(uv\right)=\left[f_T\left(u\right)f_T\left(v\right)\right]d_T\left(u,v\right)$. Thus, suppose we repeat the above process for every pair $u,v\in V\left(T\right)$. If so, then

$${\displaystyle \sum }_{uv\in E\left(T^{\prime }\right)}{w}_{T^{\prime }}\left(uv\right)={{\displaystyle \sum }}_{\left\{u,v\right\}\subseteq V\left(T\right)}\left[f_T\left(u\right)\times f_T\left(v\right)\right]d_T\left(u,v\right)=W_{\times }\left(T\right).$$

And on the other hand, one can see that $w_{T^{\prime }}\left(uv\right)=w_T{\left(uv\right)}_T[f_T\left(T_u^v\right)f_T\left(T_v^u\right)]$ for $uv\in E\left(T^{\prime }\right)$. Thus,$W_{\times }\left(T\right)=\sum _{uv\in E\left(T^{\prime }\right)}{w}_{T^{\prime }}\left(uv\right)=\sum _{uv\in E\left(T\right)}{w}_T\left(uv\right)[f_T\left(T_u^v\right)f_T\left(T_v^u\right)].$ That proves the formula of $W_{\times }\left(T\right)$. The proof for the $W_{+}$ case is quite similar. □

Corollary 4.

Assume $T$ is a $\left(f_T,w_T\right)$-weighted $n$-vertex tree. We can compute $W_{\times }\left(T\right)$ and $W_{+}\left(T\right)$ in $O\left(n\right)$-time. Moreover, if by changing the weight of $ab\in E\left(T\right)$ to $w,$ we get a tree $T^{\prime }$, then

$$W_{\times }\left(T^{\prime }\right)=W_{\times }\left(T\right)+\left(w-w_T\left(ab\right)\right)f_T\left(T_u^v\right)f_T\left(T_v^u\right),$$

$$W_{+}\left(T^{\prime }\right)=W_{+}\left(T\right)+\left(w-w_T\left(ab\right)\right)[n_T\left(T_u^v\right)f_T\left(T_v^u\right)+n_T\left(T_v^u\right)f_T\left(T_u^v\right)]$$

Remark 1.

Here, we give a simple intuition behind an algorithm for problem 1 when the tree $T$ is positively weighted. Using Lemma 5, finding a BS for $uv\in E\left(T\right)$, we need to have the $p$-Roots and $q$-Roots of $T_u^v$ and $T_v^u,$ respectively. By definition $u\in V\left(T_u^v\right)$ and $v\in V\left(T_v^u\right)$. By Corollary 3, the longest decreasing path from $u$ ends up with a $p$-Root of $T_u^v$ say $x$, and similarly, the longest decreasing path from $v$ ends up at a $q$-Root of $T_u^v$say $y$ . Moreover, by Corollary 3, those paths are the only decreasing paths in their respective components. So, one can easily take some derivatives to reach from $u$ to $x$ or from $v$ to $y$ since the paths are decreasing and unique. Then by Lemma 5, a BS of $uv$ is one of the following cases as detailed in the lemma.

• $xy$,
• an edge between  $x$  and a vertex of  $N_T\left(y\right)$,
• an edge between $y$ and a vertex of $N_T\left(x\right)$.

Lemma 5 details how to choose among the above limited cases using derivatives. As we find the unique and decreasing path between  $u$  and  $x$  and also  $v$  and  $y$, one can update  $Q_T$  as in Lemma 5. Having those paths also eases calculating  $W_{\times }$,  $W_{+}$, and  $W_{\alpha ,\beta }$ from Lemma 4. The following proposition details the mentioned intuition with proof of time complexity.

Proposition 1.

Let $T$ be an $n$-vertex positively weighted tree with a coordinate, $Q_T$. If we get $e\in E\left(T\right)$ and $w,\alpha ,\beta \in {ℝ}^{\ge 0}$, then we can compute $ϵ$, $T_{ϵ\backslash e}$, $Q_{T_{ϵ\backslash e}}$, and $W_{\alpha ,\beta }\left(T_{ϵ\backslash e}\right)$, with the worst average time of $O\left(\log n\right)$ and the best average time of $O\left(1\right)$, where $ϵ$ is a BS of $e$ w.r.t $W_{\alpha ,\beta }$ and $w_{T_{ϵ\backslash e}}\left(ϵ\right)=w$. Updating, $Q_T$ after edge-weight change to a positive number is supported in $O\left(1\right)$-time per change.

Proof. 

Assume we have an $n$-vertex positively weighted tree $T$, $Q_T=\left\{F_T,N_T,W_{\times }\left(T\right),W_{+}\left(T\right)\right\}$ and $uv\in E\left(G\right)$, $n>2$. Let $p$ and $q$ be some induced vertex weight functions for $T_u^v$ an $T_v^u$ as follows,

$$p_{\alpha ,\beta } \left(c\right)=\left[\alpha f_T\left(T_v^u\right)+\beta n_T\left(T_v^u\right)\right]h_{T_u^v}\left(c\right)+\beta f_T\left(T_v^u\right){\sigma }_{T_u^v}\left(c\right),\hspace{1em}\hspace{1em}\hspace{1em}c\in V\left(T_u^v\right),$$

$$q_{\alpha ,\beta }\left(c\right)=\left[\alpha f_T\left(T_u^v\right)+\beta n_T\left(T_u^v\right)\right]h_{T_v^u}\left(c\right)+\beta f_T\left(T_u^v\right){\sigma }_{T_v^u}\left(c\right),\hspace{1em}\hspace{1em}\hspace{1em}c\in V\left(T_v^u\right).$$

Then with the results so far, we have the following:

1. Computing a ${\mathit{p}}^{\prime }$ or ${\mathit{q}}^{\prime }$ in $\mathit{O}\left(\mathbf{1}\right)$-time. Using $F_T$ and $N_T$, Lemma 3, and Definition 2, computing $p^{\prime }\left(\overrightarrow{rs}\right)$ costs $O\left(1\right)$-time for any $rs\in P_{T_u^v}\left(u,x\right)$ where $x\in V\left(T_u^v\right)$ and we know the direction. A similar argument holds for computing $q^{\prime }$ on $P_{T_v^u}\left(v,y\right)$.

2. Checking whether a vertex is a Root on average of $\mathit{O}\left(\mathbf{1}\right)$ -time. By Corollary 3, if $p^{\prime }\left(\overrightarrow{ux}\right)<0$ for only one $x\in N_{T_u^v}\left(u\right)$, then $u$ is not a $p$-Root. The following can verify whether a vertex is $p$ or $q$-Root or not. (Let $f=p$ or $q$)

# Takes a vertex and a $f$ and says it is a $f$-Root or not

$\mathit{I}\mathit{S}\_\mathit{R}\mathit{o}\mathit{o}\mathit{t}\left(a,f\right)$

$\mathit{F}\mathit{o}\mathit{r} s\in N\left(a\right)$

$\mathit{i}\mathit{f} f^{\prime }\left(\overrightarrow{as}\right)<0$

$\mathit{r}\mathit{e}\mathit{t}\mathit{u}\mathit{r}\mathit{n} False$

$\mathit{r}\mathit{e}\mathit{t}\mathit{u}\mathit{r}\mathit{n} True$

The average degree in a tree is $O\left(1\right)$. Thus, $\mathit{I}\mathit{S}\_\mathit{R}\mathit{o}\mathit{o}\mathit{t}$ run time is $O\left(1\right)$ on average.

3. Finding a neighbor with a minimum $\mathit{p}$ or $\mathit{q}$ in $\mathit{O}\left(\mathbf{1}\right)$-time on average. If $s\in N_{T_u^v}\left(a\right)$, then by Theorem 2 and Definition 4, $p\left(s\right)=p^{\prime }\left(\overrightarrow{as}\right)w\left(as\right)+p\left(a\right)$. By 1- computing $p\left(s\right)$ takes $O\left(1\right)$-time. Moreover, $O(|N_T\left(a\right)|)=O\left(1\right)$ on average. Thus, finding $x$ with $p\left(x\right)=\underset{s\in N_{T_u^v}\left(a\right)}{min}p\left(s\right)$ takes $O\left(1\right)$-time on average. Computing min $q$ neighbor follows the same rules. One implements the mentioned idea as follows.

# Takes a vertex, $a$, finds $x\in N\left(a\right)$ with min $f$ and returns $x$ and $ax$ ($f=p$ or $q$)

$\mathit{F}\mathit{N}\mathit{D}\_\mathit{m}\mathit{i}\mathit{n}\left(a,f\right)$

$min=\infty$

$\mathit{F}\mathit{o}\mathit{r} s\in N\left(a\right)$

$f\left(s\right)=f^{\prime }\left(\overrightarrow{as}\right)w\left(as\right)+f\left(a\right)$

$\mathit{i}\mathit{f} f\left(s\right)<min$

$min=f\left(s\right)$

$x\leftarrow s$

$\mathit{r}\mathit{e}\mathit{t}\mathit{u}\mathit{r}\mathit{n} x , ax$

4. Finding, ${\mathit{P}}_{{\mathit{T}}_{\mathit{u}}^{\mathit{v}}}\left(\mathit{u},\mathit{x}\right)$ or ${\mathit{P}}_{{\mathit{T}}_{\mathit{v}}^{\mathit{u}}}\left(\mathit{v},\mathit{y}\right)$ in $\mathit{O}(\mathbf{log}\mathit{n})$ on average, where $\mathit{x}$ and $\mathit{y}$ are $\mathit{p}$ and $\mathit{q}$-Root. By Theorem 1, $T_u^v$ is $p$-convex. Assume that $P=u_1{u}_2\dots u_m$ is the decreasing path between $u=u_1$ and a $p$-Root, $u_m$. By Corollary 3, $P$ is the longest decreasing path beginning with $u$, and $p^{\prime }\left(\overrightarrow{u_{i}a}\right)<0$ if and only if $a=u_{i+1}$, $a\in N\left(v_i\right)$, $0<i<m$. So, starting with $i=1,$ we can find $u_{i+1}$ when we have $u_i$ and compute $P$ as follows:

# Takes a vertex, $a$, and returns $c$ and $P\left(a,c\right)$ where $c$ is a $f$ ($f=p$ or $q$)

$\mathit{R}\mathit{o}\mathit{o}\mathit{t}\_\mathit{P}\mathit{a}\mathit{t}\mathit{h}\left(a,f\right)$

$P\left(a,c\right)=a_1=a$

$\mathit{L}\mathit{a}\mathit{b}\mathit{l}\mathit{e}$

$\mathit{f}\mathit{o}\mathit{r} a_{i+1}\in N\left(a_i\right)\backslash a_{i-1}$

$\mathit{i}\mathit{f} f^{\prime }\left(\overrightarrow{a_i{a}_{i+1}}\right)<0$.

$P\left(a,c\right)=P\left(a,c\right)\cup a_{i+1}$

$a_i\leftarrow a_{i+1}$

$\mathit{B}\mathit{r}\mathit{e}\mathit{a}\mathit{k} \mathit{a}\mathit{n}\mathit{d} \mathit{G}\mathit{o}\mathit{t}\mathit{o} \mathit{L}\mathit{a}\mathit{b}\mathit{l}\mathit{e}$

$\mathit{r}\mathit{e}\mathit{t}\mathit{u}\mathit{r}\mathit{n} a, P\left(a,c\right)$

For finding $u_{i+1}$ from $u_i$, we can exclude $u_{i-1}$ and jump to $u_{i+1}$ as the process $\mathrm{Root}\_\mathrm{Path}$ does. That reduces the average complexity. Moreover, when we are on the vertex $u_i$, $i<m$, one takes at most |$N\left(u_i\right)|$ derivatives to find $u_{i+1}$, since we know, $u_{i+1}$ is the only vertex with negative derivatives toward it. So, $\mathrm{Root}\_\mathrm{Path}\left(u,p\right)$ returns, $P_{T_u^v}\left(u,x\right)$ by taking some derivatives, at most, as many as the total degree of the vertices on $P_{T_u^v}\left(u,x\right),$ where $x$ is a $p$-Root. By [25], the path length in a tree is $O(\log n)$ on average, where it can be $O\left(1\right)$ as well. In addition, the average degree in a tree is $O\left(1\right)$, and taking each derivative requires $O\left(1\right)$-time. Moreover, $x$ is a $p$-Root (has min $p$) and $T_u^v<T$. Thus, the worst average run time of $\mathrm{Root}\_\mathrm{Path}\left(u,p\right)$ is $O(\log n)$ and the best average time is $O\left(1\right)$. Similarly, $\mathrm{RCE}\_\mathrm{Path}\left(v,q\right)$ has the same run time to return $P_{T_v^u}\left(v,y\right)$ where $y$ is a $q$-Root.

5. Computing ${\int }_{\mathit{u}}^{\mathit{x}}{\mathit{p}}^{\prime }{\mathit{d}}_{{\mathit{T}}_{\mathit{u}}^{\mathit{v}}}$ and ${\int }_{\mathit{v}}^{\mathit{y}}{\mathit{q}}^{\prime }{\mathit{d}}_{{\mathit{T}}_{\mathit{v}}^{\mathit{u}}}$ in $\mathit{O}\left(\left|\mathit{P}\left(\mathit{u},\mathit{x}\right)\right|\right)$-time and $\mathit{O}\left(\left|\mathit{P}\left(\mathit{v},\mathit{y}\right)\right|\right)$-time, respectively. Per Definition 4, Theorem 2, and 1, if we have a path, $P=a_1{a}_2\dots a_m$, we can compute the integral of $P$ in $O\left(m\right)$-time as follows:

# Takes a path $P$ and $f$ and returns ${\int }_P^{ }{f}^{\prime }$($f=p$ or $q$)

$\mathit{I}\mathit{n}\mathit{t}\mathit{e}\mathit{g} \left(P=a_1{a}_2\dots a_m,f\right)$

${\int }_{a_1}^{a_m}{f}^{\prime }{d}_{ }=0$

$\mathit{f}\mathit{o}\mathit{r} 0<i<m$

${\int }_{a_1}^{a_m}{f}^{\prime }{d}_{ }+=f^{\prime }\left(\overrightarrow{a_i{a}_{i+1}}\right).w\left(a_i{a}_{i+1}\right)$

$\mathit{r}\mathit{e}\mathit{t}\mathit{u}\mathit{r}\mathit{n} {\int }_{a_1}^{a_m}{f}^{\prime }{d}_{ }$

6. Updating ${\mathit{F}}_{\mathit{T}}$ to ${\mathit{F}}_{{\mathit{T}}_{\mathit{x}\mathit{y}\backslash \mathit{u}\mathit{v}}}$ and ${\mathit{N}}_{\mathit{T}}$ to ${\mathit{N}}_{{\mathit{T}}_{\mathit{x}\mathit{y}\backslash \mathit{u}\mathit{v}}}$ in $\mathit{O}\left(\left|\mathit{P}\left(\mathit{u},\mathit{x}\right)\right|\right)$+$\mathit{O}\left(\left|\mathit{P}\left(\mathit{v},\mathit{y}\right)\right|\right)$ time. Per Lemma 5, $\mathit{U}\mathit{p}\_\mathit{F}\mathit{N}\left(P\left(u,x\right),f_T\left(T_v^u\right),n_T^u\left(v\right)\right)$ and $\mathit{U}\mathit{p}\_\mathit{F}\mathit{N}\left(P\left(v,y\right),f_T\left(T_u^v\right),n_T^v\left(u\right)\right)$ updates ${\mathit{F}}_{\mathit{T}}$ to ${\mathit{F}}_{{\mathit{T}}_{xy\backslash uv}}$ and ${\mathit{N}}_{\mathit{T}}$ to ${\mathit{N}}_{{\mathit{T}}_{xy\backslash uv}}$, where $\mathit{U}\mathit{p}\_\mathit{F}\mathit{N}$ is a process as follows.

# Takes a path and updates $F_T$ and $N_T$ accordingly

$\mathit{U}\mathit{p}\_\mathit{F}\mathit{N}\left(P=v_1{v}_2\dots v_m,F,N\right)$

$\mathit{f}\mathit{o}\mathit{r} 0<i<m$

$\left(n_T\left(T_{v_i}^{v_{i+1}}\right), n_T(T_{v_{i+1}}^{v_i}\right))\leftarrow \left(n_T\left(T_{v_i}^{v_{i+1}}\right)-N, n_T(T_{v_{i+1}}^{v_i}\right)+N)$

$\left(f_T\left(T_{v_i}^{v_{i+1}}\right), f_T(T_{v_{i+1}}^{v_i}\right))\leftarrow \left(f_T\left(T_{v_i}^{v_{i+1}}\right)-F, f_T(T_{v_{i+1}}^{v_i}\right)+F)$

Using the devised procedures in 1- to 6-, we can implement Lemma 4 and 5, which finds us $ϵ$, $T_{ϵ\backslash e}$, $Q_{T_{ϵ\backslash e}}$, and $W_{\alpha ,\beta }\left(T_{ϵ\backslash e}\right)$, for the input $e\in E\left(T\right)$ and $w,\alpha ,\beta \in {ℝ}^{\ge 0}$, where $ϵ$ is a BS of $e$ w.r.t $W_{\alpha ,\beta }$ and $w_{T_{ϵ\backslash e}}\left(ϵ\right)=w$. The full detail is presented with the following algorithm: BS algorithm (Algorithm 2). Each line’s average time complexity bound is shown in the results.

Preprocessing-----------------------------------------

Compute $Q_T=\left\{F_T,N_T,W_{\times }\left(T\right),W_{+}\left(T\right)\right\}$    $\#O\left(n\right)$     Corollary 1 & Lemma 6

--------------------------------------------------------------------------------------------------------------

Algorithm 2 BS Algorithm

Input: Adj list of a $\left(f_T,w_T\right)$-weighted tree $T$, $uv\in E\left(T\right)$, $Q_T$, $w,\alpha ,\beta \in {ℝ}^{+}$

Output:$xy,$ $T_{xy\backslash uv}$, $W_{\alpha ,\beta }\left(T_{xy\backslash uv}\right)$, $Q_{T_{xy\backslash uv}}$, where $xy$ is a BS of $uv$ w.r.t. $W_{\alpha ,\beta }$ and $w_T\left(xy\right)=w$

---------Finding $x,y$, $P\left(u,x\right)$ and $P\left(v,y\right)$ where $xy$ is a BS of $uv;$ (Lemma 5)-----

$\mathit{i}\mathit{f} \mathit{I}{\mathit{S}}_{\mathit{R}\mathit{o}\mathit{o}\mathit{t}\left(u,p\right)and}\mathit{I}\mathit{S}\_\mathit{R}\mathit{o}\mathit{o}\mathit{t}\left(v,q\right)\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\#O\left(1\right)$

{

$a , ua\leftarrow \mathit{F}\mathit{N}\mathit{D}\_\mathit{m}\mathit{i}\mathit{n}\left(u,p\right)\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\#O\left(1\right)$

$b , vb\leftarrow \mathit{F}\mathit{N}\mathit{D}\_\mathit{m}\mathit{i}\mathit{n}\left(v,q\right)\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\#O\left(1\right)$

$\mathit{i}\mathit{f} q^{\prime }\left(\overrightarrow{vb}\right)w_T\left(vb\right)<p^{\prime }\left(\overrightarrow{ua}\right)w_T\left(ua\right)\hspace{1em}\hspace{1em}\hspace{1em}\#O\left(1\right)$

{$x,P\left(u,x\right)\leftarrow u,u$

$y, P\left(v,y\right)\leftarrow b,vb\}$

$\mathit{e}\mathit{l}\mathit{s}\mathit{e}$

{$x,P\left(u,x\right)\leftarrow a,ua$

$y, P\left(v,y\right)\leftarrow v,v\}$

}

$\mathit{e}\mathit{l}\mathit{s}\mathit{e}$

{$x, P\left(u,x\right)\leftarrow \mathit{R}\mathit{o}\mathit{o}\mathit{t}\_\mathit{P}\mathit{a}\mathit{t}\mathit{h}\left(u,p\right)\hspace{1em}\hspace{1em}\hspace{1em}\# O\left(\log n\right) \mathrm{on} \mathrm{ave}$

$y, P\left(v,y\right)\leftarrow \mathit{R}\mathit{o}\mathit{o}\mathit{t}\_\mathit{P}\mathit{a}\mathit{t}\mathit{h}\left(v,q\right)\}\hspace{1em}\hspace{1em}\hspace{1em}\# O\left(\log n\right) \mathrm{on} \mathrm{ave}$$\# O\left(\log n\right) \mathrm{on} \mathrm{ave}$

-------------Computing $W_{\alpha ,\beta }\left(T_{xy\backslash uv}\right)$-------( Lemma 4 )-------------------------------------

$W_{\alpha ,\beta }^{\prime }\left(T_{xy\backslash uv}\right)=\mathit{I}\mathit{n}\mathit{t}\mathit{e}\mathit{g}\left(P\left(u,x\right),p_{\alpha ,\beta }\right)+\mathit{I}\mathit{n}\mathit{t}\mathit{e}\mathit{g}\left(P\left(v,y\right),q_{\alpha ,\beta }\right)+F{N}_{\alpha ,\beta }\left(uv\right)\left[w-w_T\left(uv\right)\right]$

$\#O(|P_{T_u^v}\left(u,x\right)|)+O(|P_{T_v^u}\left(v,y\right)|)$

$W_{\alpha ,\beta }\left(T\right)=\alpha W_{\times }\left(T\right)+\beta W_{+}\left(T\right) \#O\left(1\right)$

$W_{\alpha ,\beta }\left(T_{xy\backslash uv}\right)=W_{\alpha ,\beta }^{\prime }\left(T_{xy\backslash uv}\right)+W_{\alpha ,\beta }{\left(T\right)}_{ } \#O\left(1\right)$

--------$Q_T \leftarrow Q_{T_{xy\backslash uv}}$---------updating $Q_T$--------( Lemma 5 )-----------------------------

$\mathit{U}\mathit{p}\_\mathit{F}\mathit{N}\left(P\left(u,x\right),f_T\left(T_v^u\right),n_T\left(T_v^u\right)\right)\wedge \mathit{U}\mathit{p}\_\mathit{F}\mathit{N}\left(P\left(v,y\right),f_T\left(T_u^v\right),n_T\left(T_u^v\right)\right)$

$\# O(|P_{T_u^v}\left(u,x\right)\left|+ |P_{T_v^u}\left(v,y\right)\right|)$

$W_{1,0}^{\prime }\left(T_{xy\backslash uv}\right)=W_{\times }^{\prime }\left(T_{xy\backslash uv}\right)=\mathit{I}\mathit{n}\mathit{t}\mathit{e}\mathit{g}\left(P\left(u,x\right),p_{1,0}\right)+\mathit{I}\mathit{n}\mathit{t}\mathit{e}\mathit{g}\left(P\left(v,y\right),q_{1,0}\right)+F{N}_{1,0}\left(uv\right)\left[w-w_T\left(uv\right)\right]$

$\# O(|P_{T_u^v}\left(u,x\right)\left|+ |P_{T_v^u}\left(v,y\right)\right|)$

$W_{0,1}^{\prime }\left(T_{xy\backslash uv}\right)=W_{+}^{\prime }\left(T_{xy\backslash uv}\right)=\mathit{I}\mathit{n}\mathit{t}\mathit{e}\mathit{g}\left(P\left(u,x\right),p_{0,1}\right)+\mathit{I}\mathit{n}\mathit{t}\mathit{e}\mathit{g}\left(P\left(v,y\right),q_{0,1}\right)+F{N}_{0,1}\left(uv\right)\left[w-w_T\left(uv\right)\right]$

$\# O(|P_{T_u^v}\left(u,x\right)\left|+ |P_{T_v^u}\left(v,y\right)\right|)$

$W_{\times }\left(T_{xy\backslash uv}\right)=W_{\times }^{\prime }\left(T_{xy\backslash uv}\right)-W_{\times }\left(T\right)\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\#O\left(1\right)$

$W_{+}\left(T_{xy\backslash uv}\right)=W_{+}^{\prime }\left(T_{xy\backslash uv}\right)-W_{+}\left(T\right)\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\#O\left(1\right)$

---------$T\leftarrow T_{xy\backslash uv}$---------------

$T\leftarrow T+xy-uv\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\#O\left(1\right)$

--------------------------------------------------------------------------------------------------------------

Using 1 to 6 above, the average time complexity of every line of Algorithm 2. is bounded by, $\max \{O(\left|P_{T_u^v}\left(u,x\right)\left|,O(|P_{T_v^u}\left(v,y\right)\right|\right\}$. By [25], the average path length of $T$ is $O\left(\log n\right),$ which accounts for the worst average time complexity of the algorithm. The best average complexity can be $O\left(1\right)$ because $\max \{O(\left|P_{T_u^v}\left(u,x\right)\left|,O(|P_{T_v^u}\left(v,y\right)\right|\right\}$ and the degrees on $P_{T_u^v}\left(u,x\right)$ and $P_{T_v^u}\left(v,y\right)$ can be $O\left(1\right)$. Finally, assume $T\prime$ is a tree, and we have the preprocessing, $Q_{T^{\prime }}=\left\{F_{T^{\prime }},N_{T^{\prime }},W_{\times }\left(T^{\prime }\right),W_{+}\left(T^{\prime }\right)\right\}$. If we change the weight of one edge, then $F_{T^{\prime }}$ and $N_{T^{\prime }}$ remain unchanged, and by Corollary 4, we can update $W_{\times }$ and $W_{+}$ in $O\left(1\right)$-time. This completes the proof. □

The subsequent two propositions can be proved based on Proposition 1. They are indeed a solution to Problems 2 and 3, respectively.

Proposition 2.

Let $T$ be an  $n$-vertex positively weighted tree with  $E\left(T\right)={\left\{e_i\right\}}_{i=1}^n$. If we get  ${\left\{w_i,{\alpha }_i,{\beta }_i\in {ℝ}^{\ge 0}\right\}}_{i=1}^n$, then we can find an  $r$ such that  $W_{{\alpha }_r,{\beta }_r}\left(T_{{ϵ}_r\backslash e_r}\right)=min{\left\{W_{{\alpha }_i,{\beta }_i}\left(T_{{ϵ}_i\backslash e_i}\right)\right\}}_{i=1}^n$ and compute  $W_{{\alpha }_r,{\beta }_r}\left(T_{{ϵ}_r\backslash e_r}\right)$, in an average time of  $O\left(n\log n\right)$ and the best time of  $O\left(n\right)$ , where  ${ϵ}_i$ with  $w_i=w\left({ϵ}_i\right)$ is a BS of  $e_i$ w.r.t.  $W_{{\alpha }_i,{\beta }_i}$,  $0\le i\le n$.

Proposition 3.

Let $T$ be an  $n$-vertex positively weighted tree with  $E\left(T\right)={\left\{e_i\right\}}_{i=1}^n$. If we get  ${\left\{w_i,{\alpha }_i,{\beta }_i\in ℝ\right\}}_{i=1}^n$, then we can find a BS,  ${ϵ}_i$ with  $w_i=w\left({ϵ}_i\right)$ w.r.t.  $W_{{\alpha }_i,{\beta }_i}$ for all  $e_i$ and compute  $W_{{\alpha }_i,{\beta }_i}\left(T_{{ϵ}_i\backslash e_i}\right)$,  $0\le i\le n$, in an average time of  $O\left(n\log n\right)$ and the best time of  $O\left(n\right)$.

For simplicity, we avoided adding some facts for better performance of the BS algorithm. For example, by Corollary 3, a leaf is not a root of a tree with more than 2 vertices. In the BS algorithm, we either require a root or a neighbor of a root. Thus, if $T_u^v$ or $T_u^v$ are not trivial (single vertex), then the version of $T$ without the leaves can be used. That improves the actual performance of the BS algorithm.

Proposition 4.

For a simple tree $T$, there are exactly  $W\left(T\right)$ distinct switches. More precisely,

$$\left|\right\{T_{ϵ\backslash e} | \left(ϵ,e\right)\in E\left(T^c{\displaystyle \cup }T\right)\times E\left(T\right) \wedge T_{ϵ\backslash e} \mathrm{is} \mathrm{a} \mathrm{switch}\}|=W\left(T\right),$$

and if  $xy\in E\left(T^c{\displaystyle \cup }T\right)$ and  $uv\in E\left(T\right)$ ,

$$\left|\right\{T_{xy\backslash e} | e\in E\left(T\right) \wedge T_{xy\backslash e} \mathrm{is} \mathrm{a} \mathrm{switch} \}|=d_T\left(x,y\right),$$

$$\left|\right\{T_{ϵ\backslash uv} | ϵ\in E\left(T^c{\displaystyle \cup }T\right) \wedge T_{ϵ\backslash uv} \mathrm{is} \mathrm{a} \mathrm{switch} \}|=n_T\left(T_v^u\right).n_T\left(T_u^v\right).$$

Proof. 

Let $T$ be a simple tree. Using Definition 5, $xy\in E\left(T^c\right){\displaystyle \cup }E\left(T\right)$ is a switch of $e\in E\left(T\right)$, if and only if $e\in P_T\left(x,y\right)$. Otherwise, $T_{xy\backslash e}$ is disconnected, indicating that it is not a switch. Therefore, there are exactly $d_T\left(x,y\right)$ distinct switches regarding $xy\in E\left(T^c{\displaystyle \cup }T\right)$. Thus, the total number of distinct switches is as follows:

$$\begin{array}{ll}\left|\right\{T_{xy\backslash e} | \left(xy,e\right)& \in E\left(T^c\cup T\right)\times E\left(T\right) \wedge T_{xy\backslash e} \mathrm{is} \mathrm{a} \mathrm{switch}\left\}\right|\\ & ={\displaystyle \sum _{xy\in E\left(T^c\cup T\right).}}{d}_T\left(x,y\right)={\displaystyle \sum _{\left\{x,y\right\}\subseteq \in V\left(T\right)}}{d}_T\left(x,y\right)=W\left(T\right).\end{array}$$

And $\left|\right\{T_{xy\backslash e} | e\in E\left(T\right) \wedge T_{xy\backslash e} \mathrm{is} \mathrm{a} \mathrm{switch} \}|=d_T\left(x,y\right).$ In addition, $T_{ϵ\backslash uv}$ is a tree if and only if $ϵ$ is an edge between $T_u^v$ and $T_v^u$. Thus, $\left|\right\{T_{ϵ\backslash uv} | ϵ\in E\left(T^c{\displaystyle \cup }T\right) \wedge T_{ϵ\backslash uv} \mathrm{is} \mathrm{a} \mathrm{switch} \}|=n_T\left(T_v^u\right).n_T\left(T_u^v\right).$ This completes the proof. □

For $uv\in E\left(T\right)$ of a simple tree $T$ with $n$ vertices by definition, $n-1\le n_T\left(T_v^u\right).n_T\left(T_u^v\right)\le \frac{n^2}{4}$. Also, by [26,27,28], ${\left(n-1\right)}^2\le W\left(T\right)\le \left(\begin{array}{c}n+1\\ 3\end{array}\right)$.

4. Some Comparisons and Discussion

In this section, we compare our method with some existing methods. For brevity, we mean average time complexity when we talk about complexity. The compared methods are not solving the same problems that we did, but it is possible to convert them with some effort.

The top tree method can find a positively weighted tree’s median(s). It is almost equivalent to finding the Root of a tree in our method, disregarding $\alpha$ and $\beta$. Thus, for an $n$-vertex tree, $T$ and $uv\in E\left(T\right),$ we somehow can convert the top tree methods [7,8,9] to find a BS w.r.t. $W_{\alpha =1,\beta =0}$ in $O(\log n)$-time for most cases. However, if $uv$ connects a Root of $T_u^v$ and a Root of $T_v^u$, then the top tree method does not work. They also do not compute $W_{\alpha ,\beta }$ of the switches regularly, which does not let us solve problem 2 even for their specific case of $\alpha =1,\beta =0$. Generalizing the top tree method, we may be able to solve problem 1 for a fixed $\alpha ,\beta$ and compute $W_{\alpha ,\beta }$, which is overcomplicated intuitively. But, if we renew the initial values of $\alpha ,\beta$ to some $\alpha \prime ,\beta \prime$, then we have to repeat their $O\left(n\right)$-time preprocessing, which is costly. As we have seen, our method in the BS algorithm solves problem 1 in $O\left(\log n\right)$ for any $\alpha ,\beta \in {ℝ}^{\ge 0}$, computes $W_{\alpha ,\beta }^{\prime }$s, and does not require a fresh preprocessing for the change of $\alpha ,\beta$. Our method updates the preprocessing, $Q_T$ in $O\left(1\right)$-time after an edge-weight change, whereas using top trees, an edge weight update takes up to $O(\log n)$-time.

For another comparison, we borrow the solution of the best swap edge of multiple-source routing tree algorithms [15,19,20,21,29,30] for problem 3. Suppose $T$ is a spanning tree of a positively edge-weighted graph $G$ with $m$ edges and $n$ vertices. Then, in [15,19,20,21,29,30], researchers choose the BS from $E\left(G\right)-E\left(T\right)$, whereas we choose from $E\left(T^c\right)$. Therefore, by choosing $G$ to be $K_n$, the mentioned algorithms can solve problem 3. Also, they choose the BS w.r.t. as the routing cost rather than its generalization, $W_{\alpha ,\beta }$. Let $S\subseteq V\left(G\right)$ be a set of sources and $\left|S\right|>1$. Setting $f_G\left(v\right)=1$ for all $v\in S$ and $f_G\left(v\right)=0$ for all $v\in V\left(G\right)\backslash S$, results in

$$W_{1,-1}\left(G\right)=RC\left(G,S\right).$$

That is, by specifying vertices weights as mentioned and letting ${\alpha }_i=1,{\beta }_i=-1$ for $1\le i\le n$, and $G=K_n$, algorithms of [20,21] will solve problem 3. The mentioned algorithms are expensive specifically for a single failed edge, and after updating the edge weights or inserting a BS, their $O\left(n^2\right)$ preprocessing is not valid. They also do not compute $W_{\alpha ,\beta }$′s. More importantly, regarding the mentioned conversion, they solve problem 3 in more than $O\left(n^2{\log }^2 n\right)$-time and up to $O\left(n^3\right)$ depending on the number of sources, where ${\alpha }_i=1,{\beta }_i=-1,$ $1\le i\le n$ and sources are specified. In the terminology of [20,21,22], we do not limit the number of sources and, ${\alpha }_i,{\beta }_i\in R^{\ge 0}, 1\le i\le n$ , where we attain an average time of $O\left(n \log n\right)$ and the best time of $O\left(n\right)$ for Problem 3.

As a general fact, note that choosing a brute-force strategy and distance matrix for the positively edge-weighted graph, computing $W_{\alpha ,\beta }\left(T\right)$ takes $O\left(n^3\right)$. Moreover, there are between $n-1$ to $\frac{n^2}{4}$ switches regarding an edge. Therefore, using the bute-force strategy, we will need between $O\left(n^4\right)$ to $O\left(n^5\right)$ time to compute a switch with the minimum $W_{\alpha ,\beta }$. While our method executes that in $O\left(\log n\right),$ with the same flexibility. This difference is significant. Note that the existing discussed methods are comparable to ours with some constraints, but they have much less flexibility.

Our tools are general and can be applied to similar optimization problems. For instance, see [15], where we use our method for the best swap edge of spanning trees. Another interesting problem can be solving the BS problems regarding ${}_{ }{}^{k}D\left(T\right)=\sum _{\left\{u,v\right\}\subseteq V\left(T\right)}{\left(d\left(u,v\right)\right)}^k$ by considering the weight ${}_{ }{}^k\sigma {}_T\left(v\right)=\sum _{x\in V\left(T\right)}{d}_T^k\left(v,x\right)$ for the vertices of a tree, $T$. See Appendix A, where we have some computations related to the derivative and integral of, ${}_{ }{}^2\sigma {}_T$.

Finding the minimum $p$-sources routing cost spanning tree is an $NP$-hard problem for any $p>1$ and is a polynomial problem for $p=1$ [29,30,31].