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)…») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 8: | Строка 8: | ||
for all <math>u, v \in V</math>. The | for all <math>u, v \in V</math>. The | ||
parameter <math>t</math> is called a ''' stretch factor'''. | parameter <math>t</math> is called a ''' [[stretch factor]]'''. | ||
The <math>t</math>-spanner is called ''' tree <math>t</math>-spanner''', if the subgraph <math>S</math> is a | The <math>t</math>-spanner is called ''' tree <math>t</math>-spanner''', if the subgraph <math>S</math> is a | ||
Текущая версия от 17:22, 18 ноября 2024
[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.