T-Spanner: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Новая страница: «'''<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.