Warning: Undefined variable $PHP_SELF in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 2
Warning: Undefined array key "word" in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 5
Warning: Undefined array key "svar" in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 6
Warning: Undefined array key "valg" in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 7
Spanners

The MST is one of the most well-known graph structures. A MST is a network connecting all vertices of a set in such a way, that the collective weight of the edges is as low as possible.

Figure 4: MSTs are spanners

A MST. Also a spanner. And for some t also a t-spanner.

Since any tree spans all the vertices in a set it is indeed a spanner. And since it must have a stretch factor, it is also a t-spanner for some t.

The reverse, however, is not true. A t-spanner is not nescessarily a MST nor even a tree. For one thing a t-spanner can have cycles.

Figure 5: A spanner is not nescesarily a MST

Graphs using the same set of points as figure 5. Both are spanners but not trees.

The greedy algorithm presented in the following pages is nevertheless related to Kruskal's greedy algorithm for constructing MSTs. How, is explained in the greedy algorithm section.

Exercises on the t-spanner is available in the exercises section.