Unit-4

Graph-Theory

Q1)

SOLUTION: the isomorphism for the above is,

f(a)=1, f(b)=6,f(c)=8,f(d)=3,f(g)=5,f(h)=2,f(i)=4,f(j)=7.

Q2) Are the two following graphs are isomorphic?

Solution:

We check the necessary and sufficient conditions for the given graphs to be isomorphic

Condition 1: number of vertices in G1 =4

Number of vertices in G2= 4

Here both G1 and G2 have same number of vertices hence the condition satisfied.

Condition 2: number of edges in G1 = 5

Number of edges in G2 = 6

Here they are not equal, therefore the condition is not satisfied.

Hence the given graphs are not isomorphic.

Q3) If a complete graph has a total of 20 vertices, then find the number of edges it may contain.

Solution: The formula for the total number of edges in a k15 graph is given by;

Number of edges =

=

=10(19)

=190

Hence, it contains 190 edges.

Q4) If a graph has 40 edges, then how many vertices does it have?

Solution: As we know,

Number of edges = =

40 =

n(n-1) = 80

n2 – n – 80 = 0

On solving the above quadratic equation, we get;

n ≈ 9.45, -8.45

Since, the number of vertices cannot be negative.

Therefore, n ≈ 9

Q5) Find the Eulerpath for the following figure

Solution:

The graph G1has anEuler circuit for example a,e,c,d,e,b,a has Euler circuit.Neither of the graphs G2 OR G3 has Euler circuits.G3 has an Euler path but not the circuit.

Q6) The Euler path for the following figure.

Solution:

The graph H2 has a Euler circuit i.e., a,g,c,b,g,e,d,f .Neither H3 or H1 has the Euler path but namely H3  has Euler path but not the circuit.

Q7) solve the following graph for Hamilton-path.

Solution:

G1 has a Hamilton circuit at a,b,c,d,e,a. There is no Hamilton-circuit in G2 but it has a Hamilton-path.G3 neither has a Hamilton-circuit or path.

Q8) Solve the following graph using Hamilton-path

Solution:

There is no Hamilton-circuit in G because it has only one degree namely ‘e’. But it has a Hamilton-path namely e,d,a,b,c.

Now consider the graph H, where the degree of the vertices a,b,d and e are all 2every vertices incident to these vertices must be a part of Hamilton circuit. It is now easy to say that there is no Hamilton-circuit in the Graph H also .And H has a path a,b,c,d,e.

Q9) A simple graph G has 24 edges and degree of each vertex is 4. Find the number of vertices.

Solution: Given number of edges =24

Degree of each vertex =4

Let number of vertices in the graph =n

Using Hand-shaking theorem we have

Sum of degree of all vertices = 2 number of edges.

By substituting the values we get,

N 4 = 2

N =12

Thus, number of vertices in the graph =12

Q10) A graph contains 21 edges, 3 vertices of degree 4 all other vertices of degree 2. Find total number of vertices.

Solution: Given

Let number of vertices in the graph = n

Using Handshaking Theorem, we have

Sum of degree of all vertices = 2

Substituting the values, we get

3

12+2n-6=42

2n=42-6

2n=36

Thus, total number of vertices in the graph= 18

Q11) Find the minimal spanning tree of shortest distance for the following graph.

Solution:

The set sptSet (shortest path tree set)is initially empty and distances assigned to vertices are {0, INF, INF, INF, INF, INF, INF, INF} where INF indicates infinite. Now pick the vertex with minimum distance value. The vertex 0 is picked, include it in sptSet. So sptSet becomes {0}. After including 0 to sptSet, update distance values of its adjacent vertices. Adjacent vertices of 0 are 1 and 7. The distance values of 1 and 7 are updated as 4 and 8. Following sub graph shows vertices and their distance values, only the vertices with finite distance values are shown. The vertices included in SPT are shown in green color.

Pick the vertex with minimum distance value and not already included in SPT (not in sptSet). The vertex 1 is picked and added to sptSet. So sptSet now becomes {0, 1}. Update the distance values of adjacent vertices of 1. The distance value of vertex 2 becomes 12.

Pick the vertex with minimum distance value and not already included in SPT (not in sptset). Vertex 6 is picked. So sptSet now becomes {0, 1, 7, 6}. Update the distance values of adjacent vertices of 6. The distance value of vertex 5 and 8 are updated

We repeat the above steps until sptSet does include all vertices of given graph. Finally, we get the following Shortest Path Tree (SPT).

Q12)

Solution: Degree of a bounded region r = deg(r) = Number of edges enclosing the regions r.

deg(1)=3

deg(2)=4

deg(3)=4

deg(4)=3

deg(5)=8

Q13)

Solution: Degree of an unbounded region r = deg(r) = Number of edges enclosing the regions r.

deg(

deg(

Q14) Color the following graph

Solution:

Let's color the graph shown above in above figure. We will start using vertex P.

Vertex P: We will color this vertex blue.

Vertex Q: Since Q is adjacent to P, we cannot assign blue to it. We will color it red.

Vertex R: Since vertex R is adjacent to Q and P, we cannot assign blue or red to it. We will color it green.

Vertex S: Since S is adjacent to P, Q and R, we cannot assign it any of the previous colors. We will color it purple.

Q15)

Solution:

Let us color the PQRS graph in the above figure starting with vertex P.

Vertex P: Let's assign it the color blue.

Vertex Q: Q is adjacent to P. We cannot assign it the same color as P. We will color it red.

Vertex R: R is adjacent to Q. We cannot assign it the same color as Q. We will color it blue.

Vertex S: S is adjacent to P. We cannot assign it the same color as R. We will color it red.

The colored graph would look like the one in the below figure.