${k}$ -connected graph

Connectivity of graphs, when it isn’t specified which flavor is intended, usually refers to vertex connectivity, unless it is clear from the context that it refers to edge connectivity.

The (vertex) connectivity $\\kappa(G)$ is the minimum number of vertices (aka nodes) you have to remove to either make the graph no longer connected, or reduce it to a single vertex (node). $G$ is said to be $k$ -(vertex)-connected for any $k\\leqslant\\kappa(G)\\in{\\mathchoice{{\\sf I\\kern-1.2ptN}}{{\\sf I\\kern-1.2ptN}}{{%\\scriptstyle\\sf I\\kern-1.2ptN}}{{\\scriptscriptstyle\\sf I\\kern-1.2ptN}}}$ . Note that “removing a vertex” in graph theory also involves removing all the edges incident to that vertex.

The edge connectivity $\\kappa^{\\prime}(G)$ of a graph $G$ is more straightforward, it is just the minimum number of edges you have to remove to make the graph no longer connected. $G$ is said to be $k$ -edge-connected for any $k\\leqslant\\kappa^{\\prime}(G)\\in{\\mathchoice{{\\sf I\\kern-1.2ptN}}{{\\sf I\\kern-1%.2ptN}}{{\\scriptstyle\\sf I\\kern-1.2ptN}}{{\\scriptscriptstyle\\sf I\\kern-1.2ptN}}}$ . And note “removing an edge” is simply that; it does not entail removing any vertices.

•
If $\\kappa^{\\prime}(G)=0$ also $\\kappa(G)=0$ and vice versa; such graphs arecalled disconnected and consist of several connected components.If $\\kappa$ and $\\kappa^{\\prime}$ are nonzero (the graph is 1-connected) it isa connected graph (a single connected component)
•
If $\\kappa^{\\prime}(G)=1$ the graph contains at least one bridge. If $\\kappa^{\\prime}(G)>1$ (the graph is 2-edge-connected) every edge ispart of a cycle (circuit, closed path).
If $\\kappa(G)=1$ the graph contains at least one cutvertex. If $\\kappa(G)>1$ (the graph is 2-vertex-connected) there is, forany pair of vertices, a cycle they both lie on.
•
For the complete graphs we have $\\kappa(K_{n})=\\kappa^{\\prime}(K_{n})=n-1$ .
•
For any graph $G$ we have $\\kappa(G)\\leqslant\\kappa^{\\prime}(G)\\leqslant\\delta(G)$ where the latter is the minimum valency in $G$ (the valency of avertex is the number of edges sprouting from it).

Everything on this page applies equally well to multigraphs and pseudographs.

For directed graphs there aretwo notions of connectivity (http://planetmath.org/ConnectedGraph) (“weak” if the underlying graph is connected, “strong” if you can get from everywhere to everywhere).

There are nowpictures (http://planetmath.org/ExamplesOfKConnectedGraphs) to go with this entry.

单词	kconnectedGraph
释义	${k}$ -connected graph Connectivity of graphs, when it isn’t specified which flavor is intended, usually refers to vertex connectivity, unless it is clear from the context that it refers to edge connectivity. The (vertex) connectivity $\\kappa(G)$ is the minimum number of vertices (aka nodes) you have to remove to either make the graph no longer connected, or reduce it to a single vertex (node). $G$ is said to be $k$ -(vertex)-connected for any $k\\leqslant\\kappa(G)\\in{\\mathchoice{{\\sf I\\kern-1.2ptN}}{{\\sf I\\kern-1.2ptN}}{{%\\scriptstyle\\sf I\\kern-1.2ptN}}{{\\scriptscriptstyle\\sf I\\kern-1.2ptN}}}$ . Note that “removing a vertex” in graph theory also involves removing all the edges incident to that vertex. The edge connectivity $\\kappa^{\\prime}(G)$ of a graph $G$ is more straightforward, it is just the minimum number of edges you have to remove to make the graph no longer connected. $G$ is said to be $k$ -edge-connected for any $k\\leqslant\\kappa^{\\prime}(G)\\in{\\mathchoice{{\\sf I\\kern-1.2ptN}}{{\\sf I\\kern-1%.2ptN}}{{\\scriptstyle\\sf I\\kern-1.2ptN}}{{\\scriptscriptstyle\\sf I\\kern-1.2ptN}}}$ . And note “removing an edge” is simply that; it does not entail removing any vertices. • If $\\kappa^{\\prime}(G)=0$ also $\\kappa(G)=0$ and vice versa; such graphs arecalled disconnected and consist of several connected components.If $\\kappa$ and $\\kappa^{\\prime}$ are nonzero (the graph is 1-connected) it isa connected graph (a single connected component) • If $\\kappa^{\\prime}(G)=1$ the graph contains at least one bridge. If $\\kappa^{\\prime}(G)>1$ (the graph is 2-edge-connected) every edge ispart of a cycle (circuit, closed path). If $\\kappa(G)=1$ the graph contains at least one cutvertex. If $\\kappa(G)>1$ (the graph is 2-vertex-connected) there is, forany pair of vertices, a cycle they both lie on. • For the complete graphs we have $\\kappa(K_{n})=\\kappa^{\\prime}(K_{n})=n-1$ . • For any graph $G$ we have $\\kappa(G)\\leqslant\\kappa^{\\prime}(G)\\leqslant\\delta(G)$ where the latter is the minimum valency in $G$ (the valency of avertex is the number of edges sprouting from it). Everything on this page applies equally well to multigraphs and pseudographs. For directed graphs there aretwo notions of connectivity (http://planetmath.org/ConnectedGraph) (“weak” if the underlying graph is connected, “strong” if you can get from everywhere to everywhere). There are nowpictures (http://planetmath.org/ExamplesOfKConnectedGraphs) to go with this entry.
随便看	no countable dense subset of a complete metric space is a G_δ NocyclesCondition no-cycles condition Noetherian noetherian NoetherianAndArtinianPropertiesAreInheritedInShortExactSequences Noetherian and Artinian properties are inherited in short exact sequences NoetherianModule Noetherian module NoetherianRing noetherian ring NoetherianTopologicalSpace Noetherian topological space NoetherNormalizationLemma Noether normalization lemma NonabelianGroup nonabelian group Nonahedron nonahedron NonassociativeAlgebra non-associative algebra NoncentralChisquaredRandomVariable non-central chi-squared random variable NoncommutativeDynamicModelingDiagrams non-commutative dynamic modeling diagrams

k-connected graph

${k}$ -connected graph