4189
правок
Connectivity: различия между версиями
Материал из WikiGrapp
нет описания правки
KEV (обсуждение | вклад) (Создана новая страница размером '''Connectivity''' - связность) |
Glk (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Connectivity''' - | '''Connectivity''' - связность. | ||
The best known and most useful of the measures of how well a graph is | |||
conected is the '''connectivity''', defined to be the minimum number | |||
of vertices in a set whose deletion results in a disconnected ortrivial graph. | |||
Two vertices <math>u</math> and <math>v</math> in a graph <math>G</math> are said to be <math>k</math>-connected if there are <math>k</math> or more pairwise internally disjoint paths between | |||
them. The <math>(u,v)</math>-connectivity of <math>G</math>, denoted <math>k_{G}(u,v)</math>, is | |||
defined to be the maximum value of <math>k</math> for which <math>u</math> and <math>v</math> are | |||
<math>k</math>-connected. | |||
If the order of <math>G</math> is <math>p</math>, then the '''average connectivity''' of | |||
<math>G</math>, denoted <math>\bar{k}(G)</math>, is defined to be | |||
<math>k_{G} = \frac{\sum_{u,v} k_{G}(u,v)}{\left(\begin{array}{c} p 2 | |||
\end{array}\right)}.</math> | |||
(The expression <math>\sum_{u,v} k_{G}(u,v)</math> is sometimes referred to as | |||
the '''total connectivity''' of <math>G</math>.) In contrast to the connectivity, | |||
which gives the smallest number of vertices whose failure disconnects | |||
some pair of vertieces, the average connectivity gives the expected | |||
number of vertices that must fail in order to disconnect an arbitrary | |||
pair of nonadjacent vertices. | |||
==See== | |||
*''Edge connectivity, Vertex connectivity''. | |||
