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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Connected graph''' - связный граф)
 
Нет описания правки
Строка 1: Строка 1:
'''Connected graph''' - [[связный граф|связный граф]]
'''Connected graph''' --- связный граф.
 
A graph <math>G</math> is a '''connected graph''' if for all <math>u,v \in V(G)</math>, <math>u \neq v</math>, there
is a ''chain'' <math>(v_{1}, \ldots, v_{k})</math> in <math>G</math> with <math>\{v_{1},
v_{k}\} = \{u,v\}</math>, (the chain connects <math>u</math> and <math>v</math>). Otherwise, the graph is called '''disconnected'''.
 
A graph <math>G = (V,E)</math> is '''maximum edge-connected''' (in short, '''max'''-<math>\lambda</math>) if <math>\lambda = [2q/p]</math>, where <math>p = |V|, \; q = |E|</math> and
<math>\lambda = \lambda(G)</math> is ''edge-connectivity'' of <math>G</math>. Note that
the set of edges adjacent to a point <math>u</math> of degree <math>\lambda</math> is
certainly a minimum edge-disconneting set. Similarly, <math>G</math> is '''maximum point-connected''' (in short, '''max'''-<math>\kappa</math>) if <math>\kappa =
[2q/p]</math>, where <math>\kappa = \kappa(G)</math> is the point-connectivity of <math>G</math>.
Also, the set of points adjacent to <math>u</math> of degree <math>\kappa</math> is
certainly a minimum point-disconnecting set. In this context, such an
edge or a point set is called trivial. A graph <math>G</math> is called '''super edge-connected''' if <math>G</math> is max-<math>\lambda</math> and every minimum
edge-disconnecting set is trivial. Analogously, <math>G</math> is '''super point connected''' if <math>G</math> is max-<math>\kappa</math> and every minimum
point-disconnecting set is trivial.

Версия от 16:37, 11 марта 2011

Connected graph --- связный граф.

A graph [math]\displaystyle{ G }[/math] is a connected graph if for all [math]\displaystyle{ u,v \in V(G) }[/math], [math]\displaystyle{ u \neq v }[/math], there is a chain [math]\displaystyle{ (v_{1}, \ldots, v_{k}) }[/math] in [math]\displaystyle{ G }[/math] with [math]\displaystyle{ \{v_{1}, v_{k}\} = \{u,v\} }[/math], (the chain connects [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math]). Otherwise, the graph is called disconnected.

A graph [math]\displaystyle{ G = (V,E) }[/math] is maximum edge-connected (in short, max-[math]\displaystyle{ \lambda }[/math]) if [math]\displaystyle{ \lambda = [2q/p] }[/math], where [math]\displaystyle{ p = |V|, \; q = |E| }[/math] and [math]\displaystyle{ \lambda = \lambda(G) }[/math] is edge-connectivity of [math]\displaystyle{ G }[/math]. Note that the set of edges adjacent to a point [math]\displaystyle{ u }[/math] of degree [math]\displaystyle{ \lambda }[/math] is certainly a minimum edge-disconneting set. Similarly, [math]\displaystyle{ G }[/math] is maximum point-connected (in short, max-[math]\displaystyle{ \kappa }[/math]) if [math]\displaystyle{ \kappa = [2q/p] }[/math], where [math]\displaystyle{ \kappa = \kappa(G) }[/math] is the point-connectivity of [math]\displaystyle{ G }[/math]. Also, the set of points adjacent to [math]\displaystyle{ u }[/math] of degree [math]\displaystyle{ \kappa }[/math] is certainly a minimum point-disconnecting set. In this context, such an edge or a point set is called trivial. A graph [math]\displaystyle{ G }[/math] is called super edge-connected if [math]\displaystyle{ G }[/math] is max-[math]\displaystyle{ \lambda }[/math] and every minimum edge-disconnecting set is trivial. Analogously, [math]\displaystyle{ G }[/math] is super point connected if [math]\displaystyle{ G }[/math] is max-[math]\displaystyle{ \kappa }[/math] and every minimum point-disconnecting set is trivial.