1023
правки
Connected graph: различия между версиями
Материал из WEGA
нет описания правки
KEV (обсуждение | вклад) (Создана новая страница размером '''Connected graph''' - связный граф) |
KVN (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 1: | Строка 1: | ||
'''Connected graph''' | '''Connected graph''' — ''[[связный граф]].'' | ||
A [[graph, undirected graph, nonoriented graph|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 graph|disconnected]]'''. | |||
A graph <math>\,G = (V,E)</math> is '''[[maximum edge-connected graph|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|edge-connectivity]]'' of <math>\,G</math>. Note that the set of [[edge|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 graph|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 graph|trivial]]. A graph <math>\,G</math> is called '''[[super edge-connected graph|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. | |||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
