Week 9 Minimal spanning trees

Question 1

Tree

Answer 1

A tree is a finite connected graph that contains no cyclic
subgraphs.

Question 2

Forest

Answer 2

A forest is a finite graph that contains no cyclic subgraphs.

Question 3

Spanning tree

Answer 3

Let G = (V,E,ε) be a finite connected graph. A
spanning tree for G is a subgraph T = (V_T ,E_T ,ε_T ) of G
such that T is a tree and V_T = V (that is, T contains every
vertex in G).

Question 4

Length

Answer 4

Let G= (V,E,ε) be a graph equipped with a metric µ and
let E′ ⊂E be a finite subset of edges of G. The length of
E′ is defined as
l(E′) =∑_e∈E′ µ(e).

If H = (V_H ,E_H ,ε_H ) is a finite subgraph of G, then the
length of H is defined as l(H) = l(E_H ).

Question 5

Minimal spanning tree

Answer 5

A minimal spanning tree is a spanning tree T such that for
all spanning trees T′, we have l(T) ≤ l(T′).