Connectedness
Encyclopedia
In mathematics
, connectedness is used to refer to various properties meaning, in some sense, "all one piece". When a mathematical object has such a property, we say it is connected; otherwise it is disconnected. When a disconnected object can be split naturally into connected pieces, each piece is usually called a component (or connected component).
is said to be connected
if it is not the union of two disjoint nonempty open set
s. A set is open if it contains no point lying on its boundary
; thus, in an informal, intuitive sense, the fact that a space can be partitioned into disjoint open sets suggests that the boundary between the two sets is not part of the space, and thus splits it into two separate pieces.
s, Lie group
s, and graphs
are all called connected if they are connected as topological spaces, and their components are the topological components. Sometimes it is convenient to restate the definition of connectedness in such fields. For example, a graph is said to be connected if each pair of vertices
in the graph is joined by a path
. This definition is equivalent to the topological one, as applied to graphs, but it is easier to deal with in the context of graph theory
. Graph theory also offers a context-free measure of connectedness, called the clustering coefficient
.
Other fields of mathematics are concerned with objects that are rarely considered as topological spaces. Nonetheless, definitions of connectedness often reflect the topological meaning in some way. For example, in category theory
, a category
is said to be connected if each pair of objects in it is joined by a sequence of morphism
. Thus, a category is connected if it is, intuitively, all one piece.
There may be different notions of connectedness that are intuitively similar, but different as formally defined concepts. We might wish to call a topological space connected if each pair of points in it is joined by a path
. However this concept turns out to be different from standard topological connectedness; in particular, there are connected topological spaces for which this property does not hold. Because of this, different terminology is used; spaces with this property are said to be path connected. While not all connected spaces are path connected, all path connected spaces are connected.
Terms involving connected are also used for properties that are related to, but clearly different from, connectedness. For example, a path-connected topological space is simply connected
if each loop (path from a point to itself) in it is contractible; that is, intuitively, if there is essentially only one way to get from any point to any other point. Thus, a sphere
and a disk
are each simply connected, while a torus
is not. As another example, a directed graph
is strongly connected
if each ordered pair
of vertices is joined by a directed path (that is, one that "follows the arrows").
Other concepts express the way in which an object is not connected. For example, a topological space is totally disconnected if each of its components is a single point.
, a connected graph is one from which we must remove at least one vertex to create a disconnected graph. In recognition of this, such graphs are also said to be 1-connected. Similarly, a graph is 2-connected if we must remove at least two vertices from it, to create a disconnected graph. A 3-connected graph requires the removal of at least three vertices, and so on. The connectivity
of a graph is the minimum number of vertices that must be removed, to disconnect it. Equivalently, the connectivity of a graph is the greatest integer k for which the graph is k-connected.
While terminology varies, noun
forms of connectedness-related properties often include the term connectivity. Thus, when discussing simply connected topological spaces, it is far more common to speak of simple connectivity than simple connectedness. On the other hand, in fields without a formally defined notion of connectivity, the word may be used as a synonym for connectedness.
Another example of connectivity can be found in regular tilings. Here, the connectivity describes the number of neighbors accessible from a single tile
:
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, connectedness is used to refer to various properties meaning, in some sense, "all one piece". When a mathematical object has such a property, we say it is connected; otherwise it is disconnected. When a disconnected object can be split naturally into connected pieces, each piece is usually called a component (or connected component).
Connectedness in topology
A topological spaceTopological space
Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
is said to be connected
Connected space
In topology and related branches of mathematics, a connected space is a topological space that cannot be represented as the union of two or more disjoint nonempty open subsets. Connectedness is one of the principal topological properties that is used to distinguish topological spaces...
if it is not the union of two disjoint nonempty open set
Open set
The concept of an open set is fundamental to many areas of mathematics, especially point-set topology and metric topology. Intuitively speaking, a set U is open if any point x in U can be "moved" a small amount in any direction and still be in the set U...
s. A set is open if it contains no point lying on its boundary
Boundary (topology)
In topology and mathematics in general, the boundary of a subset S of a topological space X is the set of points which can be approached both from S and from the outside of S. More precisely, it is the set of points in the closure of S, not belonging to the interior of S. An element of the boundary...
; thus, in an informal, intuitive sense, the fact that a space can be partitioned into disjoint open sets suggests that the boundary between the two sets is not part of the space, and thus splits it into two separate pieces.
Other notions of connectedness
Fields of mathematics are typically concerned with special kinds of objects. Often such an object is said to be connected if, when it is considered as a topological space, it is a connected space. Thus, manifoldManifold
In mathematics , a manifold is a topological space that on a small enough scale resembles the Euclidean space of a specific dimension, called the dimension of the manifold....
s, Lie group
Lie group
In mathematics, a Lie group is a group which is also a differentiable manifold, with the property that the group operations are compatible with the smooth structure...
s, and graphs
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
are all called connected if they are connected as topological spaces, and their components are the topological components. Sometimes it is convenient to restate the definition of connectedness in such fields. For example, a graph is said to be connected if each pair of vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
in the graph is joined by a path
Path (graph theory)
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
. This definition is equivalent to the topological one, as applied to graphs, but it is easier to deal with in the context of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
. Graph theory also offers a context-free measure of connectedness, called the clustering coefficient
Clustering coefficient
In graph theory, a clustering coefficient is a measure of degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups characterised by a relatively high density of ties...
.
Other fields of mathematics are concerned with objects that are rarely considered as topological spaces. Nonetheless, definitions of connectedness often reflect the topological meaning in some way. For example, in category theory
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
, a category
Category (mathematics)
In mathematics, a category is an algebraic structure that comprises "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the category of sets, whose...
is said to be connected if each pair of objects in it is joined by a sequence of morphism
Morphism
In mathematics, a morphism is an abstraction derived from structure-preserving mappings between two mathematical structures. The notion of morphism recurs in much of contemporary mathematics...
. Thus, a category is connected if it is, intuitively, all one piece.
There may be different notions of connectedness that are intuitively similar, but different as formally defined concepts. We might wish to call a topological space connected if each pair of points in it is joined by a path
Path (topology)
In mathematics, a path in a topological space X is a continuous map f from the unit interval I = [0,1] to XThe initial point of the path is f and the terminal point is f. One often speaks of a "path from x to y" where x and y are the initial and terminal points of the path...
. However this concept turns out to be different from standard topological connectedness; in particular, there are connected topological spaces for which this property does not hold. Because of this, different terminology is used; spaces with this property are said to be path connected. While not all connected spaces are path connected, all path connected spaces are connected.
Terms involving connected are also used for properties that are related to, but clearly different from, connectedness. For example, a path-connected topological space is simply connected
Simply connected space
In topology, a topological space is called simply connected if it is path-connected and every path between two points can be continuously transformed, staying within the space, into any other path while preserving the two endpoints in question .If a space is not simply connected, it is convenient...
if each loop (path from a point to itself) in it is contractible; that is, intuitively, if there is essentially only one way to get from any point to any other point. Thus, a sphere
Sphere
A sphere is a perfectly round geometrical object in three-dimensional space, such as the shape of a round ball. Like a circle in two dimensions, a perfect sphere is completely symmetrical around its center, with all points on the surface lying the same distance r from the center point...
and a disk
Disk (mathematics)
In geometry, a disk is the region in a plane bounded by a circle.A disk is said to be closed or open according to whether or not it contains the circle that constitutes its boundary...
are each simply connected, while a torus
Torus
In geometry, a torus is a surface of revolution generated by revolving a circle in three dimensional space about an axis coplanar with the circle...
is not. As another example, a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
is strongly connected
Strongly connected component
A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. In particular, this means paths in each direction; a path from a to b and also a path from b to a....
if each ordered pair
Ordered pair
In mathematics, an ordered pair is a pair of mathematical objects. In the ordered pair , the object a is called the first entry, and the object b the second entry of the pair...
of vertices is joined by a directed path (that is, one that "follows the arrows").
Other concepts express the way in which an object is not connected. For example, a topological space is totally disconnected if each of its components is a single point.
Connectivity
Properties and parameters based on the idea of connectedness often involve the word connectivity. For example, in graph theoryGraph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a connected graph is one from which we must remove at least one vertex to create a disconnected graph. In recognition of this, such graphs are also said to be 1-connected. Similarly, a graph is 2-connected if we must remove at least two vertices from it, to create a disconnected graph. A 3-connected graph requires the removal of at least three vertices, and so on. The connectivity
Connectivity (graph theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It is closely related to the theory of network flow problems...
of a graph is the minimum number of vertices that must be removed, to disconnect it. Equivalently, the connectivity of a graph is the greatest integer k for which the graph is k-connected.
While terminology varies, noun
Noun
In linguistics, a noun is a member of a large, open lexical category whose members can occur as the main word in the subject of a clause, the object of a verb, or the object of a preposition .Lexical categories are defined in terms of how their members combine with other kinds of...
forms of connectedness-related properties often include the term connectivity. Thus, when discussing simply connected topological spaces, it is far more common to speak of simple connectivity than simple connectedness. On the other hand, in fields without a formally defined notion of connectivity, the word may be used as a synonym for connectedness.
Another example of connectivity can be found in regular tilings. Here, the connectivity describes the number of neighbors accessible from a single tile
Tile
A tile is a manufactured piece of hard-wearing material such as ceramic, stone, metal, or even glass. Tiles are generally used for covering roofs, floors, walls, showers, or other objects such as tabletops...
:
See also
- connected category
- connected component (graph theory)Connected component (graph theory)In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three connected components...
- connected sumConnected sumIn mathematics, specifically in topology, the operation of connected sum is a geometric modification on manifolds. Its effect is to join two given manifolds together near a chosen point on each...
- cross-linkCross-linkCross-links are bonds that link one polymer chain to another. They can be covalent bonds or ionic bonds. "Polymer chains" can refer to synthetic polymers or natural polymers . When the term "cross-linking" is used in the synthetic polymer science field, it usually refers to the use of...
- network
- Scale-free networkScale-free networkA scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P of nodes in the network having k connections to other nodes goes for large values of k as...
- simply connected
- small-world networkSmall-world networkIn mathematics, physics and sociology, a small-world network is a type of mathematical graph in which most nodes are not neighbors of one another, but most nodes can be reached from every other by a small number of hops or steps...
- strongly connected componentStrongly connected componentA directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. In particular, this means paths in each direction; a path from a to b and also a path from b to a....
- totally disconnected