Isomorphism :
Consider the following two graphs –
Are the graphs and
the same?
If your answer is no,then you need to rethink. The graphical arrangement of the vertices and edges makes them look different but nevertheless, they are the same graph. Also notice that the graph is a cycle, specifically
. To know about cycle graphs read Graph Theory Basics.
Formally,
“The simple graphs and
are isomorphic if there is a bijective function
from
to
with the property that
and
are adjacent in
if and only if
and
are adjacent in
.”
Example : Show that the graphs and
mentioned above are isomorphic.
Solution : Let be a bijective function from
to
.
Let the correspondence between the graphs be-
The above correspondence preserves adjacency as-
is adjacent to
and
in
, and
is adjacent to
and
in
Similarly, it can be shown that the adjacency is preserved for all vertices.
Hence, and
are isomorphic.
Proving that the above graphs are isomorphic was easy since the graphs were small, but it is often difficult to determine whether two simple graphs are isomorphic. This is because there are possible bijective functions between the vertex sets of two simple graphs with
vertices. Testing the correspondence for each of the functions is impractical for large values of n.
Although sometimes it is not that hard to tell if two graphs are not isomorphic. In order to prove that the given graphs are not isomorphic, we could find out some property which is characteristic of one graph and not the other. If they were isomorphic then the property would be preserved, but since it is not, the graphs are not isomorphic.
Such a property that is preserved by isomorphism is called graph-invariant.
Some graph-invariants include- the number of vertices, the number of edges, degrees of the vertices, and length of cycle etc.
- You can say given graphs are isomorphic if they have:
- Equal number of vertices.
- Equal number of edges.
- Same degree sequence
- Same number of circuit of perticular length
In most graphs checking first three conditions is enough.
Important Note : The complementary of a graph has the same vertices and has edges between any two vertices if and only if there was no edge between them in the original graph. Consequently, a graph is said to be self-complementary if the graph and its complement are isomorphic.
Connectivity :
Most problems that can be solved by graphs, deal with finding optimal paths, distances or other similar information. Almost all of these problems involves finding paths between graph nodes.
Path – A path of length from
to
is a sequence of
edges
such that
is associated with
, and so on, with
associated with
, where
and
.
Note : A path is called a circuit if it begins and ends at the same vertex. It is also called a cycle.
Connectivity of a graph is an important aspect since it measures the resilience of the graph.
“A undirected graph is said to be connected if there is a path between every pair of distinct vertices of the graph.”
Connected Component – A connected component of a graph is a connected subgraph of
that is not a proper subgraph of another connected subgraph of
.
For example, in the following diagram, graph is connected and graph
is disconnected. Since
is connected there is only one connected component.
But in case of there are three connected components.
In case the graph is directed, the notions of connectedness have to be changed a bit. This is because of the directions that the edges have.
Formally,
“A directed graph is said to be strongly connected if there is a path from to
and
to
where
and
are vertices in the graph. The graph is weakly connected if the underlying undirected graph is connected.”
Strongly Connected Component –
Analogous to connected components in undirected graphs, a strongly connected component is a subgraph of a directed graph that is not contained within another strongly connected component.
Articulation points –
The removal of a vertex and all the edges incident with it may result in a subgraph which has more connected components than in the original graphs. Such vertices are called articulation points or cut vertices.
Analogous to cut vertices are cut edge the removal of which results in a subgraph with more connected components. A cut-edge is also called a bridge.
Cut set – In a connected graph , a cut-set is a set of edges which when removed from
leaves
disconnected, provided there is no proper subset of these edges disconnects
.
Paths and Isomorphisms –
Sometimes even though two graphs are not isomorphic, their graph invariants- number of vertices, number of edges, and degrees of vertices all match. In this case paths and circuits can help differentiate between the graphs.
- Example – Are the two graphs shown below isomorphic?
- Solution – Both the graphs have 6 vertices, 9 edges and the degree sequence is the same. However the second graph has a circuit of length 3 and the minimum length of any circuit in the first graph is 4. Hence the given graphs are not isomorphic.
GATE CS Corner Questions
Practicing the following questions will help you test your knowledge. All questions have been asked in GATE in previous years or in GATE Mock Tests. It is highly recommended that you practice them.
1. GATE CS 2013, Question 24
2. GATE CS 2012, Question 26
3. GATE CS 2012, Question 38
4. GATE CS 2014 Set-1, Question 13
5. GATE CS 2014 Set-2, Question 61
6. GATE CS 2015 Set-2, Question 38
7. GATE CS 2015 Set-2, Question 60
References-
Graph Isomorphism – Wikipedia
Graph Connectivity – Wikipedia
Discrete Mathematics and its Applications, by Kenneth H Rosen
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments