MTH301 Final Term Solved Subjective

MTH301 Final term Solved Subjective

Question: What does it mean by the preservation of edge end point function in the definition of isomorphism of graphs?

Answer: Since you know that we are looking for two functions (Suppose one function is “f” and other function is “g”) which preserve the edge end point function and this preservation means that if we have vi as an end point of the edge ej then f(vi) must be an end point of the edge g(ej) and also the converse that is if f(vi) be an end point of the edge g(ej) then we must have vi as an end point of the edge ej. Note that vi and ej are the vertex and edge of one graph respectively where as f (vi) and g (ej) are the vertex and edge in the other graph respectively.

Question: Is there any method of identifying that the given graphs are isomorphic or not?(With out finding out two functions).

Answer: Unfortunately there is no such method which will identify whether the given graphs are isomorphic or not. In order to find out whether the two given graphs are isomorphic first we have to find out all the bijective mappings from the set vertices of one graph to the set of vertices of the other graph then find out all the bijective functions from the set of edges of one graph to the set of edges of the other graph. Then see which mappings preserve the edge end point function as defined in the definition of Isomorphism of graphs. But it is easy to identify that the two graphs are not isomorphic. First of all note that if there is any Isomorphic Invariant not satisfied by both the graphs, then we will say that the graphs are not Isomorphic. Note that if all the isomorphic Invariants are satisfied by two graphs then we can’t conclude that the graphs are isomorphic. In order to prove that the graphs are isomorphic we have to find out two functions which satisfied the condition as defined in the definition of Isomorphism of graphs.

Question: What are Complementary Graphs?

Answer: Complementary Graph of a simple graph(G) is denoted by the (G bar ) and has as many vertices as G but two vertices are adjacent in complementary Graph by an edge if and only if these two vertices are not adjacent in G .

Question: What is the application of isomorphism in real word?

Answer: There are many applications of the graph theory in computer Science as well as in the Practical life; some of them are given below. (1) Now you also go through the puzzles like that we have to go through these points without lifting the pencil and without repeating our path. These puzzles can be solved by the Euler and Hamiltonian circuits. (2) Graph theory as well as Trees has applications in “DATA STRUCTURE" in which you will use trees, especially binary trees in manipulating the data in your programs. Also there is a common application of the trees is "FAMILY TREE”. In which we represent a family using the trees. (3) Another example of the directed Graph is " The World Wide Web ". The files are the vertices. A link from one file to another is a directed edge (or arc). These are the few examples.

Question: Are Isomorphic graphs are reflexive, symmetric and transitive?

Answer: We always talk about " RELXIVITY"" SYMMETRIC" and TRANSIVITY of a relation. We never say that a graph is reflexive, symmetric or transitive. But also remember that we draw the graph of a relation which is reflexive and symmetric and the property of reflexivity and symmetric is evident from the graphs, we can’t draw the graph of a relation such that transitive property of the relation is evident. Now consider the set of all graphs say it G, this being a set ,so we can define a relation from the set G to itself. So we define the relation of Isomorphism on the set G x G.( By the definition of isomorphism) Our claim is that this relation is an " Equivalence Relation" which means that the relation of Isomorphism’s of two graphs is "REFLEXIVE" "SYMMETRIC" and "TRANSITIVE". Now if you want to draw the graph of this relation, then the vertices of this graph are the graphs from the set G. Question: Why we can't use the same color in connected portions of planar graph?

Answer: We define the coloring of graph in such a manner that we can’t assign the same color to the adjacent vertices because if we give the same colors to the adjacent vertices then they are indistinguishable. Also note that we can give the same color to the adjacent vertices but such a coloring is called improper coloring and the way which we define the coloring is known as the proper coloring. We are interested in proper coloring that’s why all the books consider the proper coloring

Question: What is meant by isomorphic invariant?

Answer: A property "P" of a graph is known as Isomorphic invariant. if the same property is found in all the graphs which are isomorphic to it. And all these properties are called isomorphic invariant (Also it clear from the words Isomorphic Invariant that the properties which remain invariant if the two graphs are isomorphic to each other).

Question: What is an infinite Face?

Answer: When you draw a Planar Graph on a plane it divides the plane into different regions, these regions are known as the faces and the face which is not bounded by the edges of the graph is known as the Infinite face. In other words the region which is unbounded is known as Infinite Face.

Question: What is "Bipartite Graph”?

Answer: A graph is said to be Bipartite if it’s set of vertices can be divided into two disjoint sets such that no two vertices of the same set are adjacent by some edge of the graph. It means that the edges of one set will be adjacent with the vertices of the other set.