Distance

Материал из WikiGrapp
Версия от 16:51, 31 марта 2011; Glk (обсуждение | вклад) (Новая страница: «'''Distance''' --- расстояние. '''1.''' The '''distance''' between two vertices <math>u, v</math>, denoted <math>d(u,v)</math>, is the length of the …»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Distance --- расстояние.

1. The distance between two vertices [math]\displaystyle{ u, v }[/math], denoted [math]\displaystyle{ d(u,v) }[/math], is the length of the shortest path between them. If no path of [math]\displaystyle{ G }[/math] connects [math]\displaystyle{ u }[/math] to [math]\displaystyle{ v }[/math], their distance is [math]\displaystyle{ \infty }[/math].

2. If [math]\displaystyle{ H_{1} }[/math] and [math]\displaystyle{ H_{2} }[/math] are subgraphs of a graph [math]\displaystyle{ G }[/math], the distance between [math]\displaystyle{ H_{1} }[/math] and [math]\displaystyle{ H_{2} }[/math] is defined as

[math]\displaystyle{ \min\{d_{G}(x,y)| \; x \in V(H_{1}), y \in V(H_{2})\}. }[/math]

3. For a vertex subset [math]\displaystyle{ S }[/math] of [math]\displaystyle{ V(G) }[/math], the distance of [math]\displaystyle{ S }[/math], denoted by [math]\displaystyle{ d(S) }[/math], is equal to the sum of the distances between all pairs of distinct vertices of [math]\displaystyle{ S }[/math]. In particular, [math]\displaystyle{ d(V(G)) = d(G) }[/math].