Mathwords logoMathwords

Weighted Tree — Definition, Formula & Examples

A weighted tree is a tree — a connected graph with no cycles — in which every edge is assigned a numerical value called its weight. These weights typically represent costs, distances, or capacities between connected nodes.

A weighted tree is an ordered pair (T,w)(T, w) where T=(V,E)T = (V, E) is a connected acyclic graph and w:E→Rw: E \to \mathbb{R} is a function that assigns a real-valued weight to each edge in EE. The total weight of the tree is ∑e∈Ew(e)\sum_{e \in E} w(e).

Key Formula

W(T)=∑e∈Ew(e)W(T) = \sum_{e \in E} w(e)
Where:
  • W(T)W(T) = Total weight of the tree
  • EE = Set of all edges in the tree
  • w(e)w(e) = Weight assigned to edge e

How It Works

Each edge in a weighted tree stores a number representing some quantity of interest, such as distance or cost. To find the total weight of a path between two nodes, you sum the weights of every edge along that path. Because a tree has exactly one path between any two vertices, the weighted distance between two nodes is unique. Algorithms like Kruskal's and Prim's produce minimum spanning trees by selecting edges that minimize total weight while keeping the graph connected and acyclic.

Worked Example

Problem: A weighted tree has 4 vertices {A, B, C, D} with edges: A–B (weight 3), A–C (weight 5), and C–D (weight 2). Find the total weight of the tree and the weighted distance from B to D.
Step 1: Compute the total weight by summing all edge weights.
W(T)=3+5+2=10W(T) = 3 + 5 + 2 = 10
Step 2: Identify the unique path from B to D: B → A → C → D.
Step 3: Sum the weights along this path to get the weighted distance.
d(B,D)=w(B,A)+w(A,C)+w(C,D)=3+5+2=10d(B, D) = w(B,A) + w(A,C) + w(C,D) = 3 + 5 + 2 = 10
Answer: The total weight of the tree is 10, and the weighted distance from B to D is 10.

Why It Matters

Weighted trees are central to network optimization. Minimum spanning trees minimize wiring cost in telecommunications, and Huffman trees (a type of weighted tree) are the basis of lossless data compression algorithms used in file formats like ZIP and JPEG.

Common Mistakes

Mistake: Confusing the total weight of a tree with the weighted distance between two specific nodes.
Correction: Total weight sums every edge in the tree. Weighted distance sums only the edges on the unique path between the two nodes in question.