T-Spanner: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''<math>t</math>-Spanner''' --- <math>t</math>-стягиватель. For any real valued parameter <math>t \geq 1</math>, a spanning subgraph <math>S = (V,E';w)…») |
(нет различий)
|
Версия от 17:59, 23 июня 2011
[math]\displaystyle{ t }[/math]-Spanner --- [math]\displaystyle{ t }[/math]-стягиватель.
For any real valued parameter [math]\displaystyle{ t \geq 1 }[/math], a spanning subgraph [math]\displaystyle{ S = (V,E';w) }[/math] with [math]\displaystyle{ E' \subseteq E }[/math] is a [math]\displaystyle{ t }[/math]-spanner of an edge-weighted graph [math]\displaystyle{ G = (V,E;w) }[/math], if
[math]\displaystyle{ d_{S}(u,v) \leq t \cdot d_{G}(u,v) }[/math]
for all [math]\displaystyle{ u, v \in V }[/math]. The parameter [math]\displaystyle{ t }[/math] is called a stretch factor.
The [math]\displaystyle{ t }[/math]-spanner is called tree [math]\displaystyle{ t }[/math]-spanner, if the subgraph [math]\displaystyle{ S }[/math] is a tree.
Obviously, for an unweighted graph, the only [math]\displaystyle{ 1 }[/math]-spanner is the graph itself.