Connectivity: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Connectivity''' - связность.
'''Connectivity''' — ''[[связность]].''


The best known and most useful of the measures of how well a graph is
The best known and most useful of the measures of how well a [[graph, undirected graph, nonoriented graph|graph]] is conected is the '''connectivity''', defined to be the minimum number
conected is the '''connectivity''', defined to be the minimum number
of [[vertex|vertices]] in a set whose deletion results in a disconnected ortrivial graph.
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
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.
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
<math>k_{G} = \frac{\sum_{u,v} k_{G}(u,v)}{\left(\begin{array}{c} p  2 \end{array}\right)}.</math>
\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==
*''Edge connectivity, Vertex connectivity''.
 
* ''[[Edge connectivity]].''
 
* ''[[Vertex connectivity]].''
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Текущая версия от 14:03, 19 марта 2015

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]\displaystyle{ \,u }[/math] and [math]\displaystyle{ \,v }[/math] in a graph [math]\displaystyle{ \,G }[/math] are said to be [math]\displaystyle{ \,k }[/math]-connected if there are [math]\displaystyle{ \,k }[/math] or more pairwise internally disjoint paths between them. The [math]\displaystyle{ \,(u,v) }[/math]-connectivity of [math]\displaystyle{ \,G }[/math], denoted [math]\displaystyle{ \,k_{G}(u,v) }[/math], is defined to be the maximum value of [math]\displaystyle{ \,k }[/math] for which [math]\displaystyle{ \,u }[/math] and [math]\displaystyle{ \,v }[/math] are [math]\displaystyle{ \,k }[/math]-connected.

If the order of [math]\displaystyle{ \,G }[/math] is [math]\displaystyle{ \,p }[/math], then the average connectivity of [math]\displaystyle{ \,G }[/math], denoted [math]\displaystyle{ \bar{k}(G) }[/math], is defined to be

[math]\displaystyle{ k_{G} = \frac{\sum_{u,v} k_{G}(u,v)}{\left(\begin{array}{c} p 2 \end{array}\right)}. }[/math]

(The expression [math]\displaystyle{ \,\sum_{u,v} k_{G}(u,v) }[/math] is sometimes referred to as the total connectivity of [math]\displaystyle{ \,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

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.