Exams Prep Master
We've all played the connecting the dots puzzle game as children. But what does this puzzle game have to do with connectivity in mathematics? The concept of connectivity is related to the concept of linking. In the same way that we link one dot to another to complete a drawing in this puzzle game, similarly, we link one vertex to another in a graph so that it can be traversed. As a result, the Connected graph can be explained as a fundamental concept in the theory of connectivity graphs. The connectivity of the graph determines whether or not the graph can be traversed. Here, we will be learning about connectivity in-depth and discussing some important questions.
| Table of Content |
Key Takeaways: Connectivity, Connected Graphs, Disconnected Graphs, Edge Connectivity, Vertex Connectivity, Cut Vertex, Cut Edge, Cut Set.
Meaning of Connectivity
[Click Here for Sample Questions]
Connectivity is one of the core principles of graph theory in mathematics and computer science; it asks for the fewest number of components, such as nodes or edges, that must be eliminated in order to separate the remaining nodes into two or more independent subgraphs.
The term "connectivity" can refer to a variety of applications in everyday life. It is widely known as the joining of two or more entities or attributes. The definition of connectivity is different in various fields and subjects, some of the definitions in different fields are mentioned below.
- The Algebraic connectivity of a graph G is the second-smallest eigenvalue of the Laplacian matrix of G (counting multiple eigenvalues individually). If and only if G is a linked graph, this eigenvalue is greater than 0.
- The capacity to connect systems or application programs is known as connectivity in the field of Information Technology. To execute operations or properly balance resources at an installation, application applications may need to communicate with one another.
- Connectivity in Management platform is intended to assist enterprises to build and scale their IoT using a managed cellular connectivity service by reducing operational workload.
- Pixel connectivity in Image Processing refers to how pixels in two-dimensional images interact with their neighbors.
Also Read: Distance Time Graph
Connectivity in Graphs
[Click Here for Sample Questions]
A graph is said to be connected if a path exists between every pair of vertex pairs. There should be a path that connects every vertex to every other vertex. This is referred to as a graph's connectivity. A disconnected graph is one that has multiple disconnected vertices and edges.
As in the given image, one can travel from ‘A’ to ‘C’ but can not travel from ‘E’ to any of the given points
Also Read:
Properties of Connectivity
[Click Here for Sample Questions]
- The connected graph is known as an undirected graph because it has at least one path connecting each pair of vertices.
- If a graph has multiple disconnected vertices and edges, it is said to be disconnected.
- The graph that is connected by three vertices is known as a 1-vertex connected graph because removing any of the vertices causes the graph to disconnect.
- If the removal of one edge in connected graph results in the disconnection of a graph, the graph is referred to as a 1-edge connected graph.
- If there is a set (say S) of edges (or vertices) in a connected graph such that removing all of set S's edges results in a disconnected graph. The set S is then referred to as a cut set. If S is made up of vertices, it is referred to as a vertex-cut set. Similarly, if it has edges, it is referred to as an edge-cut set.
- A bi-connected graph is a connected graph with two vertices and two disjoint paths connecting these two vertices.
- In network applications such as routing transportation networks, network tolerance, and so on, graph connectivity theories are essential.
Also Read: Statistics
Connected Graphs in Mathematics
[Click Here for Sample Questions]
There are different types of graphs in Mathematics, some important types are mentioned below.
Vertex Connectivity
A connected graph's connectivity (or vertex connectivity). G is the smallest number of vertices that, when removed, cause G to disconnect or reduce to a trivial graph. It is represented by the letter K. (G). When K(G) k, the graph is called a k-connected or k-vertex connected. In order to remove a vertex, we must also remove the edges that are adjacent to it.
Edge Connectivity
In graph theory, when the smallest number of edges are removed from a graph in order to disconnect it then it is referred to as edge connectivity. It is denoted by the symbol (G). As a result, if λ(G) ≥ k, then the graph G will be called k-edge-connected.
Cut Vertex
A cut-vertex is a single vertex whose removal breaks a graph.
Let G be a connected graph. A vertex ‘v’ of G is called a cut vertex of G if G-v (Remove v from G) results in a disconnected graph.
When we remove a vertex from a graph, it will split into two or more graphs. This is referred to as a cut vertex.
Cut Edge
A cut-edge or bridge is a single edge that disconnects a graph when it is removed.
Assume G is a connected graph. If G-e (Remove e from G) results in a disconnected graph, an edge e of G is called a cut edge of G.
When we remove an edge from a graph, it splits into two or more graphs. This removal edge is referred to as a cut edge or bridge.
Cut Set
A cut set in a connected graph G is a set S of edges if removing all of the edges in S disconnects G and removing some of the edges in S does not disconnect G.
Facts about Connectivity and Graphs
[Click Here for Sample Questions]
- As early as the 1300s, graphs were used to describe mathematical relationships.
- World Statistics Day is celebrated on the 29th of June every year.
- Prasanta Chandra Mahalanobis is the father of Indian Statistics.
- William Playfair invents the line chart and bar chart, as well as statistical graphics.
Things to Remember
- Connectivity is widely known as the joining of two or more entities or attributes.
- The connectivity of the graph determines whether or not the graph can be traversed.
- A graph is said to be connected if and only if it has one connected component.
- A disconnected graph is an undirected graph that is not connected.
Also Read: Mathematics Preparation Tips
Sample Questions
Ques: What is the basic property of connectivity in a graph? (2 marks)
Ans: A graph is said to be connected if and only if it has one connected component. A graph is also said to be connected if every pair of vertices in it is connected. This means that every pair of vertices has a path between them.
Ques: What is a disconnected graph? (2 marks)
Ans: A disconnected graph is an undirected graph that is not connected. For example, a cut vertex or a cut edge disconnects a graph when it is removed.
Ques: What is a vertex connectivity in a graph? (2 marks)
Ans: The vertex connectivity k(G) of a graph G, also known as "point connectivity" or simply "connectivity," is the smallest size of a vertex cut, i.e., a vertex subset S subset= V(G) such that G-S is disconnected or has only one vertex.
Ques: What is an edge connectivity in a graph? (2 marks)
Ans: The number of edges λ(G) that must be removed from a graph G to disconnect G, also known as line connectivity. A disconnected graph has no edge connectivity, whereas a connected graph with a graph bridge has one.
If k(G) is the graph's vertex connectivity and δ(G) is its minimum degree, then for any graph,
k(G) ≤ λ(G) ≤ δ(G).
Ques: Demonstrate that a graph is connected if and only if it has a spanning tree. (2 marks)
Ans: If there is a spanning tree, the graph is clearly connected, such that, for any vertices u and v, there will be a u-v path in the tree, and thus a u-v path in the graph.
If the graph is connected, the Breadth-First Search algorithm finds a spanning tree, proving the existence of a spanning tree.
Ques: Prove that every connected graph with n 2 vertices has a vertex that can be removed without causing the remaining graph to be disconnected. (2 marks)
Ans: Considering the spanning tree T of a graph. It has at least two leaves.
Let's call them x and y.
Then T x and T y are both connected, and their supergraphs, G x, and G y are as well.
Ques: Find the number of edges that a complete graph can have if it has a total of 20 vertices. (2 marks)
Ans: The formula for the total number of edges in a k15 graph is as follows:
Edge count = n/2(n-1)
= 20/2(20-1)
=10(19)
=190
As a result, it has 190 edges.
Ques: What is the number of vertices in a graph if it has 40 edges? (2 marks)
Ans: We know that the number of edges = n/2 (n-1)
40 = n/2 (n-1)
n(n-1) = 80
n2 – n – 80 = 0
Solving the above quadratic equation, we get: n=9.45, -8.45
Because the number of vertices can never be negative, the number of vertices n ≈ 9.
Ques: Demonstrate that the graphs G and G` mentioned in the diagram are isomorphic. 
(4 marks)
Ans: Let f be a bijective function ranging from V to V`.
Let the relationship between the graphs be,
v1` = f (v1)
v2` = f (v5)
v3` = f (v3)
v4` = f (v4)
v5` = f (v2)
The preceding correspondence maintains adjacency as-
In G, v1 is next to v2 and v3, and In G`, f(v1) = v1` is adjacent to f(v2) = v5 and f(v3) = v3.
Similarly, it is possible to demonstrate that the adjacency is preserved for all vertices.
As a result, G and G` are isomorphic.
Mathematics Related Links:
Comments