4624
правки
Connectivity: различия между версиями
Материал из WikiGrapp
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 6: | Строка 6: | ||
Two vertices <math>\,u</math> and <math>\,v</math> in a graph <math>\,G</math> are said to be [[k-Connected vertices|<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. | Two vertices <math>\,u</math> and <math>\,v</math> in a graph <math>\,G</math> are said to be [[k-Connected vertices|<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 | 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>\,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> | <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. | (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== | ==See== | ||
