Connected graph

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

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


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