# Connected graph

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

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.