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

For a vertex and edge weighted (VEW) graph G with a vertex weight function f G let W α , β ( G ) = ∑ { u , v } ⊆ V ( G ) [ α f G ( u ) × f G ( v ) + β ( f G ( u ) + f G ( v ) ) ] d G ( u , v ) where, α , β ∈ ℝ and d G ( u , v ) denotes the distance, the minimum sum of edge weights across all the paths connecting u , v ∈ V ( G ) . Assume T is a VEW tree, and e ∈ E ( T ) fails. If we reconnect the two components of T − e with new edge ϵ ≠ e such that, W α , β ( T ϵ \ e = T − e + ϵ ) is minimum, then ϵ is called a best switch (BS) of e w.r.t. W α , β . 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 ∈ E ( T ) and w , α , β ∈ ℝ + , we return ϵ , T ϵ \ e , and W α , β ( T ϵ \ e ) with the worst average time of O ( log n ) and the best time of O ( 1 ) where ϵ is a BS of e w.r.t. W α , β and the weight of ϵ is w .