What if not connectedness defines a graph?

709 Views Asked by At

I am studying graphs through an online course and came across the idea of a "connected component", a "subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the subgraph."

This means that a single graph need not be connected. So my question is: what, if not connectivity, defines a graph and separates it from another graph? And as an aside, if there is no such boundary, is it ever useful to think of all graphs being connected?

4

There are 4 best solutions below

0
On BEST ANSWER

Matt Pressland has given a good answer, but I'd just like to add on that in math the notion of a "collection" of objects is given a lot of weight. Collections have their own independent existence, and are not second-class citizens. For example, for any set $A$, the set $\{A\}$ is a totally different object, even though it appears we've only given it a "wrapper". Similarly, with a graph, $$\color{red}{\fbox{$\genfrac{}{}{0pt}{}{\Large \strut\bullet\texttt{----}\bullet}{\Large \strut\bullet}$}}$$ is a graph with two connected components, while $$\color{blue}{\fbox{$\strut \bullet\texttt{----}\bullet$}}\\ \color{green}{\fbox{$\strut\bullet$}}$$ is two different connected graphs that happen to have been drawn near to each other.

0
On

The notion of two graph being "separate" (distinguishable) can be defined formally in terms of non-existence of a graph isomorphism between them.

While connectedness of a graph is preserved under graph isomorphisms, so we may speak of connectedness as a useful property in distinguishing graphs, it is not enough to decide whether two graphs are "the same" (isomorphic). It does make sense to begin by trying to count the number of connected components in each graph, so that if that count disagrees, the two graphs are not isomorphic, but recognizing a graph isomorphism turns out to be harder than just counting the components.

A basic category of graphs whose definition requires connectedness is Tree. A graph whose connected components are Trees is called a Forest.

0
On

This may sound silly, but what defines a particular graph is the definition of that graph; i.e. the description of its vertices and edges and how they are connected to each other. It is possible that given all of this data, it will turn out that the resulting graph is disconnected, and that's just the way it is. If the graph is disconnected, then the various connected components are also (connected) graphs - these are different graphs (from each other and the original graph), because they have a different set of vertices and edges.

The point is that it is not usually useful to think of a disconnected graph as not being a graph at all, but as a union of different graphs. This is because a graph is often used as a pictorial or combinatorial representation of the data of some objects and relationships between them, and the graph being disconnected represents some piece of information about that data, so we should allow it to happen.

Sometimes people will assume all graphs are connected to prove certain results, even if the result is true for disconnected graphs - this is most common if the results are only being applied to connected graphs, or if the result for a disconnected graph follows more or less immediately from the result applied to each connected component.

0
On

Imagine the graph representing the bones of the human body which are connected by joints. Now, there is a single bone, the Hyoid bone, which is not connected to any other bone. Therefore, there will be no edge to another bone. The vertex representing that bone is still part of the graph but it is disconnected, disjoint.

You can even have a graph with only vertexes and no edges, in which NONE of the graph is connected and it is still a graph.

To distinguish two graphs, you have to look at its vertexes and its edges. If two graphs are different, one thing to notice is that they have a different number of vertices or a different number of edges. Then, you need to see how their vertices are connected by those edges. Even if they're in the same configuration (called isomorphic), unless their vertexes are equal, they are different graphs.

For example, a graph of 28 unrelated people and a graph of 28 unrelated fruits are different graphs because the vertices of the first graph are people and the vertices of the second graph are fruits.