4189
правок
Connected graph: различия между версиями
Материал из WEGA
нет описания правки
KEV (обсуждение | вклад) (Создана новая страница размером '''Connected graph''' - связный граф) |
Glk (обсуждение | вклад) Нет описания правки |
||
| Строка 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. | |||
