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.