Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

enter image description here

This cut induced confuses me.... I dont really understand what it is saying...

enter image description here

I am not understanding what connectivity is in graph theory. I thought connectivity is when you have a tree because all the vertices are connected but the above mentions something weird like components could someone please explain what they are and what connectivity really is?

share|improve this question
tree no because graph,let's say undriected graph(it means there exist direct path from x to y,but not vice versa)may has cycle (starting and ending point is same),so conectivity is like when you can pass vertexes(some number of vertex and egde and come to destination) –  dato datuashvili Apr 13 '12 at 9:49
add comment

3 Answers

up vote 2 down vote accepted

Connectivity and components

Intuitively, a graph is connected if you can't break it into pieces which have no edges in common. More formally, we define connectivity to mean that there is a path joining any two vertices - where a path is a sequence of vertices joined by edges. The example of $Q_3$ in your question is obviously not connected - none of the vertices in the bit on the left are connected to vertices in the bit on the right. Alternatively, there is no path from the vertex marked 000 to the vertex marked 001.

(As an aside - all trees are connected - a tree is defined as a connected graph with no cycles. But there are many other connected graphs.)

So if a graph is not connected, then we know it can be broken up into pieces which have no edges in common. These pieces are known as components. The components are themselves connected - they are called the maximal connected subgraphs because it is impossible to add another vertex to them and still have a connected graph. All connected graphs have only one component - the graph itself.

Cut induced

You can think of the cut induced as being the set of edges which connect some collection of vertices to the rest of the graph. In the diagram you give, the set called $A$ is the collection of vertices within the dotted line. The cut induced by $A$ is then the collection of edges which cross the dotted line - the edges which connect the vertices inside the dotted line to those outside it. Edges joining vertices inside the shaded area are not part of the cut induced, and neither are edges joining vertices on the outside of the dotted line.

More formally, the complement of $A$ is exactly those vertices which are not in $A$. So the cut induced by $A$ is the collection of edges joining vertices in $A$ to vertices in the complement of $A$.

share|improve this answer
I should have added - you can think of the cut induced by $A$ as being those edges which you would have to cut through if you wanted to separate $A$ from the rest of the graph (i.e., the complement of $A$). –  Donkey_2009 Apr 13 '12 at 14:38
add comment

The connectivity means as the definition says that there is at least a path from any vertex $x$ to any vertex $y$, which intuitively means that you can "walk" from any vertex to any other one in the graph -this is similar to path-connectivity in topology-.

Obviously, not every graph is connected. For example, take any connected graph you know and consider the graph given by the sum or union of these two copies, it is obvious that there is not path from vertices on one copy to the vertices in the other copy.

In these cases, it is interesting to consider subgraphs that are connected in these disconnected graphs to see how much disconnected are they. In this situation what ones want is to have connected subgraphs that are not contain in any connected subgraph, these are precisely the connected componets of a graph.

These components are nothing more than a useful concept, since it can be proven that given a vertex in graph you have a path only to those vertices in the same component. This gives another way of seeing waht a component is, given a vertex $x$ the component containing $x$ is the induce subgraph by all the vertices to which at least a path exists from $x$ in the graph.

share|improve this answer
add comment

Yes, a tree is, in particular, a connected graph - one in which every pair of vertices can be connected by exactly one simple path (i.e. a path with no repeated vertices). A connected graph is something more general - it is simply one in which every pair of vertices can be connected by at least one (simple) path.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.