 | This article needs additional citations for verification .(July 2016) (Learn how and when to remove this template message) |
In mathematics, connectedness [1] 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).
A topological space is said to be connected if it is not the union of two disjoint nonempty open sets. [2] 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.
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, manifolds, Lie groups, 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 morphisms. 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 condition turns out to be stronger than 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.
Properties and parameters based on the idea of connectedness often involve the word connectivity. For example, in graph theory, a connected graph is one from which we must remove at least one vertex to create a disconnected graph. [3] 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:
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 non-empty open subsets. Connectedness is one of the principal topological properties that are used to distinguish topological spaces.
In topology and related branches of mathematics, a topological space may be defined as a set of points, along with a set of neighbourhoods for each point, satisfying a set of axioms relating points and neighbourhoods. The definition of a topological space relies only upon set theory and is the most general notion of a mathematical space that allows for the definition of concepts such as continuity, connectedness, and convergence. Other spaces, such as manifolds and metric spaces, are specializations of topological spaces with extra structures or constraints. Being so general, topological spaces are a central unifying notion and appear in virtually every branch of modern mathematics. The branch of mathematics that studies topological spaces in their own right is called point-set topology or general topology.
This is a glossary of some terms used in the branch of mathematics known as topology. Although there is no absolute distinction between different areas of topology, the focus here is on general topology. The following definitions are also fundamental to algebraic topology, differential topology and geometric topology.
In mathematics, general topology is the branch of topology that deals with the basic set-theoretic definitions and constructions used in topology. It is the foundation of most other branches of topology, including differential topology, geometric topology, and algebraic topology. Another name for general topology is point-set topology.
In graph theory, a component of an undirected graph is an induced subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the rest of the graph. For example, the graph shown in the illustration has three components. A vertex with no incident edges is itself a component. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are also sometimes called connected components.
This is a glossary of graph theory terms. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by edges.
In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.
In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges.
In topology and related areas of mathematics, a topological property or topological invariant is a property of a topological space which is invariant under homeomorphisms. That is, a property of spaces is a topological property if whenever a space X possesses that property every space homeomorphic to X possesses that property. Informally, a topological property is a property of the space that can be expressed using open sets.
In the mathematical field of graph theory, the term "null graph" may refer either to the order-zero graph, or alternatively, to any edgeless graph.
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements that need to be removed to separate the remaining nodes into isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.
In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph.
In the mathematical discipline of graph theory, the dual graph of a plane graph G is a graph that has a vertex for each face of G. The dual graph has an edge whenever two faces of G are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.
In mathematics, a pair of pants is a surface which is homeomorphic to the three-holed sphere. The name comes from considering one of the removed disks as the waist and the two others as the cuffs of a pair of pants.
In topology and other branches of mathematics, a topological space X is locally connected if every point admits a neighbourhood basis consisting entirely of open, connected sets.
In graph theory, a connected graph G is said to be k-vertex-connected if it has more than k vertices and remains connected whenever fewer than k vertices are removed.
In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.
In mathematics, and more specifically in graph theory, a directed graph is a graph that is made up of a set of vertices connected by edges, where the edges have a direction associated with them.
In mathematics, a topos is a category that behaves like the category of sheaves of sets on a topological space. Topoi behave much like the category of sets and possess a notion of localization; they are a direct generalization of point-set topology. The Grothendieck topoi find applications in algebraic geometry; the more general elementary topoi are used in logic.
In the mathematics of infinite graphs, an end of a graph represents, intuitively, a direction in which the graph extends to infinity. Ends may be formalized mathematically as equivalence classes of infinite paths, as havens describing strategies for pursuit-evasion games on the graph, or as topological ends of topological spaces associated with the graph.