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
A spanner is a graph, G(V, E), with one particular property: The edges, E, create a network connecting all vertices, V.
As such, both the complete graph and a minimum spanning tree qualify as spanners.
Figure 2: Graph types
The complete graph and a Minimum Spanning Tree (MST). Both are spanners.
The t-spanner
A t-spanner is a subset of spanners with one additional property: The shortest path between any two vertices is not too long.
To be more specific, the length of a shortest path between two vertices is at most t times their euclidian distance.
We will define the detour factor of two points as the length of a shortest path between them in proportion to their euclidian distance.
To describe a t-spanner, one could say that:
- the detour when travelling from one point to another is not too long,
- the minimum distance travelled between any two points is at most t times the euclidian distance, or
- the detour factor between any two points is at most t.
The largest detour factor in the graph is called the stretch factor of the graph. Thus, the stretch factor of a t-spanner must be weakly less than t. In other words, t is an upper bound of the stretch factor.
In the complete graph all vertices are connected directly. Since there are no forced detours the stretch factor is 1. Furthermore, there is no way of lowering the stretch factor below 1.
This leads us to conclude, that 1 is a lower bound of t.