What does connected components mean in the context of non-graphs? Graphs have vertices and the vertices are connected by edges. Hence, you can build a spanning tree (for example) by systematically joining connected components (where connected components refer to connected subgraphs).

Previous discussion on this topic reveals that each connected component of a linear decision tree on some function F represents a particular region bounded by a set of half-planes and hyperplanes. For linear decision trees applied to the element uniqueness problem, we have 2 possible type of connected components (correct me if I'm wrong) - YES and NO components.

Apparently there is only 1 NO component, and at least n! YES components when for linear decision trees applied to the element uniqueness problem on a set of "n" distinct items. I can understand the number of YES components (simply permute all items), but I'm not sure why there's only 1 NO component.


Connected components are a concept of topology. Under the usual topology on $\mathbb{R}^n$, we say that two points $x,y \in S$ belong to the same connected component if there is a path from $x$ to $y$ which is entirely in $S$ (this is known as path-connectedness). This defines an equivalence relation on $S$, and a connected component of $S$ is an equivalence class of this relation. This generalizes the graphical definition which is more familiar to this audience.

| cite | improve this answer | |
  • $\begingroup$ Thank you! The explanation is simple, but clear. $\endgroup$ – J. Firs Aug 7 '17 at 6:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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