QB 060010212

060010212-Advanced Mathematics for Computer Application
2016

Unit-1: Matrix Algebra
Short questions answer
1. What is Matrix?
2. Define the following terms :
a) Elements matrix
b) Row matrix
c) Column matrix
d) Diagonal matrix
e) Scalar matrix
f) Unit matrix OR Identity matrix
g) Triangular matrix
h) Comparable matrices
i) Equality of matrices
j) Skew-symmetric matrix
3. If A is a matrix of order p × q and B is a matrix of order q × r, then what is the order of
the product of matrix AB?
4. What is the necessary condition for the addition of two matrices?
5. “Every identity matrix is a diagonal matrix” True or False? Justify your answer.
6. “Matrix multiplication is always commutative” True or False? Justify your answer.
7. What is necessary condition for matrix multiplication?
8. Find the inverse of matrix shown below.
2 0

0 0
9. State the difference between a matrix and a determinant.
10. List out special types of matrices.
11. Define inverse of a matrix.
12. Give the condition for the existence of the inverse.
13. List out the properties of the inverse of a matrix.
14. Which are the properties of the transpose of a matrix?
15. What do you mean by the principal diagonal of the matrix?
16. What is transpose of a matrix?
−3 8 3 −8
17. If A= and B= , find B-A.
3 5 3 −5
2 −3
18. If P= , find BT.
−1 9
1 0
19. If B = , find 2B and -3B.
4 7
2 3 5 1
20. If A= and B= , find AB and BA. Is AB=BA?
1 4 0 3
Long questions answer
7 3 −5
1. If A = 0 4 2 and B=3A; C=B+2A-5I. Find matrix D such that D=2A+B-C.
1 5 4
Mr. Nikhil Choksi Page 1

060010212-Advanced Mathematics for Computer Application 2016

6 3
2. If A = −3 9 find the matrix B such that 2AT+3B=0.
12 −6
3. Find AB and BA.
1 −1 1 1 2 3
Where A = −3 2 −1 and B = 2 4 6
−2 1 0 1 2 3
2 6 −3 5 4 7
4. If A = B = and C = prove that A(BC) = (AB)C.
7 2 0 8 9 5
1 3
1 2 3 −4
5. If A = 0 2 and B = find AB.
2 0 −2 1
−1 4
0 4 3
6. If A = 1 −3 −3 prove that A2=I.
−1 4 4
1 2 2
7. If A = 2 1 2 satisfies the following equation: A2-4A-5I=O. Where O is a null matrix
2 2 1
and I is a unit matrix.
4
8. If A = 1 2 3 and B = 5 find AB and BB’.
6
1 −1 1 𝑥
9. If A = , B = and (A+B)2 = A2 + B2, find x and y.
2 −1 4 𝑦
10. Find adjoint of the following matrices:
2 −5
a)
7 9
−4 3
b)
8 7
2 −1 3
c) 1 1 1
1 −1 1
5 −6 4
d) 7 4 −3
2 1 6
11. Find the inverse of the following matrices:
2 3
a)
5 −7
2 −3
b)
4 −1
𝑎 𝑏
c)
𝑐 𝑑
−1 −2 3
d) −2 1 1
4 −5 2


2 −1 4
e) −3 0 1
−1 1 2
1 1 1
f) 1 2 −3
2 −1 3
3 7
12. If A = , find A + AT + A-1.
2 5
3 1 5 6 0
13. If A = , B = show that (AB)-1 = B-1A-1.
2 4 0 1 2
4 1 1 0
14. If A = and AB = , find matrix B.
7 2 0 1
5 6 −7 5 0
15. Find the transpose of : 4 3 0 1 2
−6 2 1 −3 −4
2 5 7 1 4 9
16. If A = 2 −1 0 B = 3 −2 4 verify that (i) (A + B)T = AT + BT and (ii) (AB)T = BTAT.
3 4 8 −5 6 8
17. Find the inverse of the following matrices and verify that AA-1 = I.
2 1 −1
a) 1 0 −1
1 1 2
6 3
b)
4 5
18. Give three differences between determinant and matrix each with example.
19. Discuss laws of Matrix Algebra.
20. Explain special types of matrices.

Multiple Choice Questions
2 4 6
1. If A = , the order of matrix A is
8 5 3
a) 3 × 2
b) 2 × 3
c) 1 × 3
d) 3 × 1
2. If A = 1 2 3 , which type of the given matrix B?
a) Unit matrix
b) Row matrix
c) Column matrix
d) Square matrix
1 −2 4
3. Mention the type of the matrix A = −2 3 5
4 5 8
a) Symmetric matrix
b) Skew-symmetric matrix
c) Null matrix
d) Identity matrix


0 0
4. is matrix of the type:
0 0
a) zero matrix
b) row matrix
c) column matrix
d) unit matrix
1 0
5. is matrix of the type:
0 1
a) zero matrix
b) unit matrix
c) row matrix
d) column matrix
4 −5 2
6. If A = 0 6 9 , the diagonal elements are:
2 7 8
a) 4, 6, 8
b) 4, 0, 2
c) 2, 6, 2
d) All of the above
1 4 −2 −1
7. If A = , B = then, A – 2B – I gives
2 5 3 0
4 6
a)
4 6
−4 −6
b)
−4 −6
4 6
c)
−4 6
4 6
d)
4 −6
2 4 1
8. If B = 4 −6 3
0 6 4
a) -2
b) 2
c) 6
d) -6
3 2 1 0
9. If A = , B = , the product BA is
4 1 3 1
a) None of the above
3 2
b)
13 −7
3 −2
c)
13 −7
−3 2
d)
13 7
1 2
10. If A = , then adj. A is:
3 −4
−4 −2
a)
−3 −1


4 2
b)
3 1
−4 −2
c)
−3 1
4 2
d)
3 −1
2 −3
11. If B = , then transpose of B is:
1 6
2 1
a)
3 6
2 1
b)
−3 6
2 −3
c)
1 6
2 3
d)
1 −6
4 5
12. If A = ,then (AT)T is:
−2 3
4 −2
a)
5 3
4 5
b)
−2 3
4 5
c)
2 3
d) None of the above
2 3
13. If A = , then A-1 is:
5 −2
a) (1/-19)A
b) A
c) (1/19)A
d) –A
1 −1 1
14. If A = 2 −1 0 , then A3 is:
1 0 0
a) I2
b) I4
c) I3
𝑎 𝑏
15. If A = then, adj(adj(A)) gives:
𝑐 𝑑
a) –B
b) adj. B
c) B
d) (1/2)B
3 −6
16. If A = , then |A| =
2 −4
a) -12
b) 12
c) 0
Fill in the blanks
1. A (n) __________________ is an arrangement of numbers in rows and columns.


2. The individual quantities like a11, a22, a13.....amn are called the ___________ of the
matrix.
3. If there are m rows and n columns in the matrix then order of matrix is ___________.
4. If we interchange rows and columns of a matrix A, the new matrix obtained is known as
the _______________ of matrix A and it is denoted by _____.
5. A matrix in which there is only one row and any number of columns is said to be
__________ matrix.
6. A matrix in which there is only one column and any number of rows is said to be
___________ matrix.
7. If all the elements of matrix are zero is known as _______ matrix.
8. A matrix in which number of rows and number of columns are _________ is said to be a
square matrix.
9. If the transpose of a square matrix gives the same matrix is known as
________________ matrix.
10. Each diagonal elements of a skew symmetric matrix must be __________.
11. A square matrix in which all diagonal elements are ___________ and all other elements
are ___________ is known as an identity matrix.
12. If all elements except diagonal elements of a square matrix are zero the matrix is said to
be __________________ matrix.
13. The addition or subtraction of two or more matrices is possible only when they are of
the _______________.
14. If A is a matrix of order m × n and B is a matrix of order n × p, then product AB will be a
matrix of order __________________.
15. In _______________ the number of rows and columns are equal.
16. In _______________ the number of rows and columns are not necessarily equal.
17. A determinant has __________.
18. A matrix cannot have __________.
19. The __________ of any element of a matrix can be obtained by eliminating the row and
column in which that element lies.
20. __________ of a square matrix is the transpose of the matrix of the co-factors of a given
matrix.

True-False
1. If A be a matrix of order of 3 × 2, then there are 3 columns and 2 rows in the matrix A.
2. A matrix is an arrangement of numbers in rows and columns.
3. The matrix is denoted by small letters like a, b, c etc.
4. The element of ith row and jth column is denoted by aij.
5. Two matrices are said to be equal only if the number of rows in both matrices should be
equal.
6. A matrix in which there is only one column and any number of rows is said to be a row
matrix.
7. A matrix in which there is only one column and any number of rows is said to be a
column matrix.


8. A zero matrix can be a row matrix or a column matrix.
9. Each diagonal element of a skew symmetric matrix must be zero.
10. In a skew symmetric matrix diagonal elements are non-zero.
11. If all elements except diagonal elements of a square matrix are zero the matrix is said to
be a diagonal matrix.
12. The addition or subtraction of two or more matrices is possible only when they are of
the same order.
13. The scalar product of a matrix is obtained by multiplying each element of first row of the
matrix by that scalar.
14. For the multiplication of two matrices A and B, the number of columns of matrix A and
the number of rows of matrix B should not be equal.
15. The matrix multiplication is commutative.
16. If A and B any two matrices of any order m × n, then A + B = B + A.
17. If A, B, c be any three matrices of the same order m × n, then A + C = B + C gives A=B.
18. Adjoint of a square matrix is the transpose of the matrix of the co-factors of a given
matrix.
19. In Equal matrices, the order of both matrices is not necessarily in the same order.
20. In determinant the number of rows and columns are equal.
21. In matrix the number of rows and columns are not necessarily equal.
22. A matrix has a value and a determinant cannot have a value.

Unit-2: Group Theory
1. What is an algebraic system?
2. Define n-ary operation.
3. State the closure property of a binary operation with an example.
4. Define identity, inverse and idempotent elements of an algebraic system with proper
examples.
5. What is homomorphism with respect to an algebraic system?
6. Define isomorphism with respect to an algebraic system.
7. What is Binary operation?
8. Define sub-algebraic system with an example.
9. Define direct product of two algebraic systems.
10. Define semi group and monoid with an example for each.
11. Give an example of a set which is closed under certain binary operation but a subset of
which may not closed under the same operation.
12. Define sub-semi group and sub-monoid with an example for each.
13. Define a group with an example.
14. State the basic properties of a group.
15. Define the order of a group and order of an element of a group.
16. Define a dihedral group.


17. Give name of some properties satisfied by algebraic systems.
18. Define a cyclic with an example.
19. How many generators are there for a cyclic group of order 8? What are they?
20. Define a permutation group.
1. If * is the binary operation on the set R of real numbers defined by a * b = a+b+2ab,
a) Find if {R, *} is a semi group. Is it commutative?
b) Find the identity element, if exists.
c) Which elements have inverses and what are they?
2. If N is the set of positive integers and * denotes the least common multiple on N, show
that {N, *} is a commutative semi group. Find the identity element of *. Which elements
in N have inverses and what are they?
3. If Q is the set of rational numbers and * is the operation on Q defined by
a * b = a + b – ab , show that {Q, *} is a commutative semi group. Find also the identity
element of *. Find the inverse of any element of Q if it exists.
4. If * is the operation defined on S = Q × Q, the set of ordered pairs of rational numbers
and given by (a, b) * (x, y) = (ax, ay + b),
a) Find if (S, *) is a semi group. Is it commutative?
b) Find the identity element of S.
c) Which elements, if any, have inverses and what are they?
5. If S = N × N, the set of ordered pairs of positive integers with the operation * defined by
(a, b) * (c, d) = (ad + bc, bd) and if f: (S, *) → (Q, +) is defined by f(a, b) = a/b, show that f
is a semi group homomorphism.
6. Show that the set Q+ of all positive rational numbers forms an abelian group under the
operation * defined by a * b = 1/2ab; a, b ∈ Q+.
7. Prove that the set {1, 3, 7, 9} is an abelian group under multiplication modulo 10.
8. Show that the set {Zm} of equivalence classes modulo m is an abelian group under the
operation +m of addition modulo m.
9. If {G, *} is an abelian group, show that (a * b)n = an * bn, for all a, b ∈ G, where n is a
positive integer.
10. Define the dihedral group (D4, *) and give its composition table.
11. Show that, if {Un} is the set of nth roots of unity, {Un, X} is a cyclic group. Is it abelian?
12. Show that every group of order 3 is cyclic and every group of order 4 is abelian.
13. Show that the set of all polynomials in x under the operation of addition is a group.
14. Prove that the set {0, 1, 2, 3, 4} is a finite abelian group of order 5 under addition
modulo 5 as composition.
15. If * is defined on Q+ such that a * b = ab/3, for a, b ∈ Q+, show that {Q+, *} is an abelian
group.
16. Show that the group {(1, 2, 4, 5, 7, 8), X9} is cyclic. What are its generators?
17. If * is defined on Z such that a * b = a + b + 1 for a, b ∈ Z, show that {Z, *} is an abelian
group.
18. Show that the group {(1, 3, 3, 4, 5, 6), X7} is cyclic. How many generators are there for
this group? What are they?


19. If R is the set of real numbers and * is the operation defined by a * b = a + b + 3ab,
where a, b ∈ R, show that {R, *} is a commutative monoid. Which elements have
inverses and what are they?
20. If Z6 is the set of equivalence classes generated by the equivalence relation “congruence
modulo 6”, prove that {Z6, X6} is a monoid where the operation X6 and Z6 is defined as
[i] X6 [j] = [(i X j) (mod 6)], for any [i], [j] ∈ Z6. Which elements of the monoid are
invertible?

1. Usual Subtraction is not binary operation on the set is
a) Z
b) R
c) N
d) Q
2. (R, X) is not Group because
a) X is not associative on R
b) identity element does not exists in R with respect to X
c) inversion property is not satisfied
3. If a group satisfied commutative property then it is known as
a) abelian group
b) symmetric group
c) semi group
d) monoid
4. A semi group (G, *) is said to be monoid if
a) * is associative
b) * is commutative
c) There exists identity element with respect to *.
d) Every element of G has inverse with respect to *.
5. An isomorphism g: {X, •} → {Y, *} is called an automorphism if:
a) Y=X
b) Y→X
c) X↔Y
d) X≤Y

Fill in the blanks
1. A system consisting of a non-empty set and one or more n-ary operations on the set is
called a (n) _________________.
2. An algebraic system will be denoted by _______________.
3. If S is a non-empty set and * be a binary operation on S, then the algebraic system {S, *}
is called _____________, if the operation * is ______________.
4. If a semi group {M, *} has an identity element with respect to the operation *, then
{M, *} is called ________________.
5. The identity element of a group (G, *) is ___________.


6. The inverse of each element of (G, *) is ____________.
7. A (n) _______________ mapping of a non-empty set S→S is called a permutation of S.
8. The set of G of all permutations on a non-empty set S under the binary operation * of
the right composition of permutations is a group {G, *} called the _____________ group.
9. The dihedral group is denoted by ____________.
10. The set of transformations due to all rigid motions of a regular motions of a regular
polygon of n sides resulting in identical polygons but with different vertex names under
the binary operation of right composition * is a group called _________________.
11. A group {G, *} is said to be ______________, if there exists an element a ∈ G such that
every element x of G can be expressed as x = an for some integer n.
12. The cyclic group is generated by a or a is a generator of G, which is denoted by
_____________.
13. A cyclic group is ___________.
14. A group homomorphism f is called group isomorphism, if f is _____________ and
_____________.
15. An isomorphism g: {X, •} → {Y, *} is called an automorphism, if ______________.

True-False
1. Every monoid is semi group.
2. Every binary operation satisfied closure property.
3. In a group there may be an element which has two inverses.
4. If the homomorphism g: {X, •} → {Y, *} is one-one, the g is called an epimorphism.
5. If the homomorphism g: {X, •} → {Y, *} is onto, then g is called a monomorphism.
6. If g: {X, •} → {Y, *} is one-one and onto then g is called an isomorphism.
7. A homomorphism g: {X, •} → {Y, *} is called an endomorphism, if Y=X.
8. An isomorphism g: {X, •} → {Y, *} is called an automorphism, if Y=X.
9. Composition of two homomorphisms is also a homomorphism.
10. The set of all semi group endomorphism of a semi group is not a semi group under the
operation of composition.
11. The set of idempotent elements of a commutative monoid {M, *, e} forms a submonoid
of M.
12. The identity element of a group (G, *) is not unique.
13. The inverse of each element of (G, *) is unique.
14. The cancellation laws are false in a group.
15. (a * b)-1 = b-1 * a-1.
16. (G, *) can have an idempotent element except the identity element.
17. A cyclic group is abelian.
18. If a is a generator of a cyclic group {G, *}, a-1 is not a generator of {G, *}.
19. A group homomorphism f is called group isomorphism, if f is one-to-one and onto.
20. If S is a non-empty set and * be a binary operation on S, then the algebraic system {S, *}
is called semi group, if the operation * is commutative.



Unit-3: Basics of Graph Theory
1. Define: Simple graph.
2. What do you mean by multigraph?
3. What is pseudo graph? Give an example.
4. What do you mean by degree of a vertex?
5. What are the degrees of an isolated vertex and a pendant vertex?
6. State the hand-shaking theorem.
7. Define in-degree and out-degree of a vertex?
8. What is meant by source and sink in graph theory?
9. Define complete graph and give an example.
10. Define regular graph. Can a regular graph can be a complete graph?
11. Can a complete graph be a regular graph? Establish your answer by 2 examples.
12. Define n-regular graph. Give one example for each of 2-regular and 3-regular graphs.
13. Define a bipartite with an example.
14. In what way a completely bipartite graph differs from a bipartite graph?
15. Draw K5 and K6.
16. Define a sub graph and spanning sub graph.
17. What is an induced sub graph?
18. Draw K2, 3 and K3,3 graphs.
19. What do you mean by proper sub graph of G?
20. Give an example of pendent vertex.

1. Determine whether the following graphs shown has directed or undirected edges,
whether it has multiple edges, or whether it has one or more loops?
a) b) c) d)

2. Determine whether the following graphs shown has directed or undirected edges,
whether it has multiple edges, or whether it has one or more loops?
a) b) c)

3. Does there exist, a simple graph with 5 vertices of the given degrees below? If so draw


such a graph.
(a) 1, 2, 3, 4, 5; (b) 1, 2, 3, 4, 4; (c) 3, 4, 3, 4, 3; (d) 0, 1, 2, 2, 3; (e) 1, 1, 1, 1, 1.
4. Find the number of vertices, number of edges, and degree of each vertex in the
following undirected graphs. Identify all isolated and pendant vertices.

5. Find the number of vertices, number of edges, and degree of each vertex in the
following undirected graphs and hence, verify the Handshaking Theorem for each one:


6. Find the number of vertices, number of edges, in-degree and out-degree of each vertex
in the following directed graphs and hence, verify that the sum of in-degrees, the sum of
out degrees of the vertices and the number of edges in the following graphs are equal.
7. Draw the graphs: K7, K1,8, K4,4,C7, W7, Q4.

8. How many sub-graphs with at-least one vertex do (a) K2 (b) K3, (c) W3 have?
9. Determine whether each of these degree sequences represents a simple graphs or not?
If the graph is possible, draw such a graph.
(a) 5,4,3,2,1,0; (b) 6,5,4,3,2,1; (c) 2,2,2,2,2,2; (d) 3,3,3,2,2,2; (e) 3,3,2,2,2,2;
(f) 1,1,1,1,1,1; (g) 5,3,3,3,3,3; (h) 5,5,4,3,2,1; (i) 3,3,3,3,2; (j) 4,4,3,2,1.
10. Represent the following graphs using adjacent matrices:

(a) (b) (c) (d)


(e) (f) (g)
(h) (i) (j) (k)
(l) (m) (n)

1. A graph, in which there is only an edge between pair of vertices, is called a
a) simple graph
b) pseudo graph
c) multi graph
d) weighted graph
2. Which sub-graph of graph G needs not contain all its edges?
a) Proper
b) Spanning
c) Induced


d) Vertex deleted
3. The Handshaking theorem is true for which of the following graphs.
a) Directed
b) Undirected
c) Complete
d) Directed simple
4. The adjacency matrices of two graphs are identical only if the graphs are:
a) simple
b) isomorphic
c) bipartite
d) complete
5. A graph in which loops and parallel edges are allowed is called:
a) simple graph
b) pseudo graph
c) multi graph
d) weighted graph
6. Graph in which a number is assigned to each edge are called:
a) regular graph
b) pseudo graph
c) multi graph
d) weighted graph
7. If there is pendent vertex in graph, if the degree of a vertex is:
a) zero
b) two
c) one
d) four
8. A vertex with zero in degree is called:
a) source
b) sink
c) pendent vertex
d) isolated vertex
9. A vertex with zero out degree is called:
a) source
b) sink
c) pendent vertex
d) isolated vertex
10. A simple graph in which there is exactly one edge between each pair of distinct vertices,
is called:
a) regular graph
b) simple graph
c) complete graph
d) bipartite graph



Fill in the blanks
1. ______________ are discrete structures consisting of vertices and edges that connect
these vertices.
2. A node of a graph which is not adjacent to any other node is called a(n)
________________ node.
3. A graph containing only isolated nodes is called a(n) _____________ graph.
4. If in graph G = (V, E), each edge e ∈ E is associated with an ordered pair of vertices, then
G is called a ________________.
5. If each edge is associated with an unordered pair of vertices, then G is called a(n)
________________ graph.
6. An edge of a graph that joints a vertex to itself is called a(n) _______________.
7. If, in a directed or undirected graph, certain pairs of vertices are joined by more than
one edge, such edges are called _______________ edges.
8. A graph, in which there is only one edge between a pair of vertices, is called
an________________ graph.
9. A graph which contains some parallel edges is called an ________________.
10. A graph in which loops and parallel edges are allowed is called an
___________________.
11. Graphs in which ______________ is assigned to each edge are called weighted graphs.
12. The degree of an isolated vertex is ______________.
13. If the degree of a vertex is ______________, it is called a pendant vertex.
14. The number of edges with v as their initial vertex is called the _____________ and is
denoted as _________________.
15. A vertex with zero in degree is called an ____________ and a vertex with zero out
degree is called an ________________.
16. A simple graph, in which there is exactly one edge between each pair of distinct vertices
is called a _______________ graph.
17. If every vertex of a simple graph has the __________ degree, then the graph is called a
regular graph.
18. If each vertex of V1 is connected with every vertex of V2 by an edge, then G is called an
_________________________ graph.
19. In a directed graph, the number of edges with v as their terminal vertex is called the
_____________and is denoted as ______________.
20. The pair of nodes that are connected by an edge are called ________________.

True-False
1. A simple graph has no loops; each diagonal entry of the adjacency matrix is 0.
2. In loop, the initial and terminal nodes are one and the same.
3. A row with all 0 entries in an incidence matrix of a graph corresponds to a pendant
vertex.
4. A completely bipartite graph need not be a simple graph.
5. All vertex deleted sub-graphs are spanning sub-graphs.
6. The adjacency matrix of a pseudo-graph is a symmetric matrix.


7. There are 18 sub-graphs of K3 containing at-least one vertex.
8. The pair of nodes that are connected by an edge are called adjacent nodes.
9. A node of a graph which is not adjacent to any other node is called an isolated node.
10. A graph containing only isolated nodes is called an undirected graph.
11. If each edge is associated with an unordered pair of vertices, then graph G is called a
directed graph.
12. An edge of a graph that joints another vertex is called a loop.
13. In a directed graph, certain pairs of vertices are joined by more than one edge; such
edges are called parallel edges.
14. A graph in which there is more than one edge between pair of vertices is called a simple
graph.
15. A graph which contains some parallel edges is called a multigraph.
16. A graph in which loops and parallel edges are allowed is called a weighted graph.
17. Graphs in which a number is assigned to each edge are called pseudo graph.
18. If the degree of a vertex is one or more, it is called a pendant vertex.
19. A vertex with zero in degree is called a sink.
20. A vertex with zero out degree is called a source.
21. A simple graph, in which there is exactly two edge between each pair of distinct vertices
is called a complete graph.
22. If every vertex of a simple graph has the same degree, then the graph is called a regular
graph.

Unit-4: Graphs Isomorphism, Path and Circuits
1. Define graph isomorphism.
2. Give an example of isomorphic graphs.
3. What is the invariant property of isomorphic graphs?
4. Give an example to show that the invariant conditions are not sufficient for graph
isomorphism.
5. Define a path and the length of a path.
6. When is a path said to be simple path? Give an example for each of general path and
simple path.
7. Define a circuit. When is it called a simple circuit?
8. Define a connected graph and a disconnected graph with example.
9. What do you mean by connected components of a graph?
10. State the condition for the existence of a path between two vertices in a graph.
11. Find the maximum number of edges in a simple connected graph with n vertices.
12. How will you find the number of paths between any two vertices of a graph analytically?
13. Define Eulerian path and Eulerian circuit of a graph, with an example for each.
14. State the necessary and sufficient condition for the existence of an Eulerian circuit in a
connected graph.
15. When a graph is called an Eulerian graph?
16. Define Hamiltonian path and Hamiltonian circuit with examples.


17. When a graph is called Hamiltonian graph?
18. State an invariant in terms of circuits of two isomorphic graphs.
19. State the necessary and sufficient condition for the existence of an Eulerian path in a
connected graph.
20. Give the definition of a strongly connected directed graph with an example.
21. Define weakly connected directed graph with an example.
22. What is meant by a strongly connected component of a diagraph?
23. What are the advantages of Warshall’s algorithm over Dijkstra’s algorithm for finding
shortest paths in weighted graph?
24. Find the number of Hamiltonian circuits in K33.


1. Represent each of these graphs with adjacency matrices:
(a) K4; (b) K1,4; (c) K2,3; (d) C4; (e) W4; (f) Q3
2. Draw the graphs with the given adjacency matrix:

(a) (b) (c) (d) (e) (f)
(g)

(h) (i)

3. Represent the incidence matrix for the following graphs:

(a) (b) (c) (d)


(e)

(f) (g)

4. Determine whether the given graphs are isomorphic or not? Justify by giving appropriate
Reasons

(a)

(b)

(c)
(d)


(e)
(f)

(g) (h)

(i)

(j) (k)


11. Determine whether the given pair of directed graphs is isomorphic?

(a) (b)

(c) (d)

12. Draw a call graph for the telephone numbers 555-0011, 555-1221, 555-1333, 555-8888,
555-2222, 555-0091, and 555-1200 if there were three calls from 555-0011 to 555-8888,
two calls from 555-8888 to 555-0011 and two calls from 555-2222 to 555-0091 two calls
from 555-1221 to each of the other numbers, and one call from 555-1333 to each of
555-0011, 555-1221 and 555-1200

13. Draw the graphs represented by the following incidence matrices:


14. Give the step by step procedure of Dijktra’s algorithm to find the shortest path between
any two vertices.
15. Find the shortest path from the vertices a to z in the following graph model:

16. Find the shortest path for the graph model given below:



19. The diagram below shows roads connecting towns near to Rochdale. The numbers on


each arc represent the time, in minutes, required to travel along each road. Peter is
delivering books from his base at Rochdale to Stockport. Use Dijkstra’s algorithm to find
the minimum time for Peter’s journey.

20. The diagram below shows roads connecting villages near to Royton. The numbers on
each arc represent the distance, in miles, along each road. Leon lives in Royton and
works in Ashton. Use Dijkstra’s algorithm to find the minimum distance for Leon’s
journey to work.

1. A matrix whose rows are the rows of the unit matrix, but not necessarily in their natural
order, is called:
a) adjacency matrix
b) adjacency matrix of pseudo graph
c) adjacency matrix of simple graph
d) permutation matrix
2. If the edges in a path are distinct, it is called:
a) simple path
b) simple graph
c) length of the path
d) simple cycle
3. The maximum number of edges in a simple disconnected graph G with n vertices and k
components is:
a) (n-k)/2
b) (n-k+1)/2


c) (n-k)(n-k+1)/2
d) (n-k)(n-k-1)/2
4. Which of the following statement is true for connected graph:
a) A connected graph contains an Euler path, if and only if each of its vertices is of
even degree.
b) A connected graph contains an Euler circuit, if and only if each of its vertices is of
odd degree.
c) A connected graph contains an Euler path, if and only if it has exactly four
vertices of odd degree.
d) A connected graph contains an Euler path, if and only if it has exactly two
vertices of odd degree.
5. A directed graph is said to be strongly connected if:
a) There is a path between every two vertices in the underlying undirected graph.
b) For any pair of vertices of the graph, at least one of the vertices of the pair is
reachable from the other vertex.
c) There must be a sequence of directed edges from any vertex in the graph to any
other vertex.
d) There is always a path between every two vertices when the directions of the
edges are disregarded.

Fill in the blanks
1. Two graphs G1 and G2 are said to be ________________ to each other, if there exists a
0ne-to-one correspondence between the vertexes sets which preserves adjacency of
the vertices.
2. Two graphs are isomorphic, if and only if their vertices can be labelled in such a way that
the corresponding adjacency matrices are ___________.
3. An ____________in a graph is a finite alternating sequence of vertices and edges,
beginning and ending with vertices, such that each edge is incident on the vertices
preceding and following it.
4. If the edges in a path are distinct, it is called a _____________ path.
5. The number of edges in a path is called the ______________ of the path.
6. If the ______________ and ______________ vertices of a path are the same, the path is
called a circuit or cycle.
7. A graph that is not connected is called ________________.
8. The disjoint connected sub graphs are called the _____________ of the graph.
9. A path of graph G is called a _______________ path, if it includes each edge of G exactly
once.
10. A circuit of graph G is called a ______________ circuit, if it includes each edge of G
exactly once.
11. A connected graph contains an Euler circuit, if and only if each of its vertices is of
____________ degree.
12. A connected graph contains an Euler path, if and only if it has exactly two vertices of


___________ degree.
13. A path of a graph G is called a________________ path, if it includes each vertex of G
exactly once.
14. A circuit of a graph G is called a ________________ circuit, if it includes each vertex of G
exactly once, except the starting and end vertices which appear twice.
15. A graph containing a Hamiltonian circuit is called a ________________ graph.
16. A graph may contain __________________ Hamiltonian circuit.
17. A directed graph is said to be _____________, if there is a path between every two
vertices in the underlying undirected graph.
18. A simple directed graph is said to be ________________, if for any pair of vertices of the
graph, at least one of the vertices of the pair is reachable from the other vertex.
19. The maximum number of edges in a simple disconnected graph G with n vertices and k
components is ______________________.
20. Any strongly connected directed graph is also ______________.
21. A _______________ path between two vertices in a weighted graph is a path of least
weight.
22. In a _________________ graph, a shortest path means one with the least number of
edges.

True-False
1. Two graphs with same vertices and same edges are always isomorphic.
2. The number of vertices of odd degree in an undirected graph is even.
3. In the graph K3,3 the degree of each vertex in the graph is degree 3.
4. Two graphs are isomorphic, if and only if their vertices can be labelled in such a way that
the corresponding adjacency matrices are different.
5. A matrix, whose rows are the rows of the unit matrix, but not necessarily in their natural
order, is called a permutation matrix.
6. If the edges in a path are equal, it is called a simple path.
7. The number of vertices in a path is called the length of the path.
8. If the initial and final vertices of a path are the distinct, the path is called a cycle.
9. A simple directed graph is said to be strongly connected, if for any pair of vertices of the
graph, at least one of the vertices of the pair is reachable from the other vertex.
10. If the initial and final vertices of a simple path of non-zero length are the same, the
simple path is called a simple circuit.
11. A graph that is not connected is called disconnected.
12. A disconnected graph is the intersection of two or more connected sub graphs.
13. The maximum number of edges in a simple disconnected graph G with n vertices and l
components is (n-k)/2.
14. A path of graph G is called an Eulerian path, if it includes each edge of G exactly once.
15. A connected graph contains an Euler circuit, if and only if each of its vertices is of odd
degree.
16. A connected graph contains an Euler path, if and only if it has exactly two vertices of
even degree.


17. A graph contains exactly one Hamiltonian circuit.
18. A directed graph is said to be weakly connected, if there is a path between every two
vertices in the underlying undirected graph.
19. A Hamiltonian path contains a Hamiltonian circuit, but a graph containing a Hamiltonian
path need not have a Hamiltonian circuit.
20. A shortest path between two vertices in a weighted graph is a path of least weight.
21. In an unweighted graph, a shortest path means one with the most number of edges.

Unit - 5 : Trees
Short question answer
1) Define following.
a. Tree
b. Forest
c. Rooted Tree
d. Sub-tree
e. Parent of vertex v in a rooted tree
f. Child of vertex v in a rooted tree
g. Sibling of vertex v in a rooted tree
h. Ancestor of vertex v in a rooted tree
i. Descendant of vertex v in a rooted tree
j. Internal vertex
k. Leaf
l. Level of a vertex
m. Height of a vertex
n. m-ary tree
o. Full m-ary tree
p. Complete m-ary tree
2) Give an example of a full 3-ary tree.
3) How many leaves and internal vertices does a full binary tree with 25 total vertices
have?
4) What are the maximum and minimum heights of a binary tree with 25 vertices have?
5) In each of the following cases, state whether or not such a tree is possible.
i. A binary tree with 35 leaves and height 100.
ii. A full binary tree with 21 leaves and height 21.
iii. A binary tree with 33 leaves and height 5.
iv. A rooted tree of height 5 where every internal vertex has 3 children and
there are 365 vertices.
6) Given two vertices in a tree, how many distinct simple paths can we find between the
two vertices?
7) State few properties of tree.
8) How many vertices are there in a tree with 19 edges?


9) How many edges are there in a tree with 16 vertices?
10) How many vertices are there in a tree with 20 edges?
11) Does there exist a tree T with 8 vertices such that the total degree of G is 18? Justify
your answer.
12) Give an example of a graph that satisfies the specified condition or show that no such
graph exists.
13) A tree with six vertices and six edges.
14) A tree with three or more vertices, two vertices of degree one and all the other vertices
with degree three or more.
15) A disconnected graph with 10 vertices and 8 edges.
16) A disconnected graph with 12 vertices and 11 edges and no cycle.
17) A tree with 6 vertices and the sum of the degrees of all vertices is 12.
18) A connected graph with 6 edges, 4 vertices, and exactly 2 cycles.
19) A graph with 6 vertices, 6 edges and no cycles.
Long Question answer
1) Which of the given graphs are trees?

2) Which of the given graphs are trees?

3) Answer the following questions about the rooted trees given below:

(a) Which vertex is the root? (b) Which vertices are internal?


(c) Which vertices are leaves? (d) Which vertices are children of j?
4) Construct a complete binary tree of height 4 and a complete 3-ary tree of height 3.
5) Answer the following questions about the rooted trees given below:

(a) Which vertices are descendants of b?
(b) Is the rooted tree a full m-ary tree for some positive integer m?
(c) What is the level of each vertex of the rooted tree?
(d) Draw a sub-tree of the tree in the given tree figures that is rooted at (a) a; (b) c
6) How many edges does a tree with 10,000 vertices have?
7) How many vertices does a fully binary tree with 1000 internal vertices have?
8) How many leaves does a fully 3-ary tree with 100 vertices have?
9) How many edges does a full binary tree with 1000 internal vertices have?
10) Draw the sub tree of the tree that is rooted at “a, c, e”

11) Draw the sub tree of the tree that is rooted at “a, c, e”

12) What is the level of each vertex of the rooted tree


13) What is the level of each vertex of the rooted tree

14) Suppose there exists a simple connected graph with 16 vertices that has 15 edges. Does
it contain a vertex of degree 1? Justify your answer.
15) Draw a tree with two vertices of degree 3. Find the number of vertices of degree 1 in
your tree.
16) Draw a graph having the given properties or explain why no such graph exists.
a) Tree; six vertices having degree 1,1,1,1,3,3
b) Tree; all vertices of degree 2
c) Tree; 10 vertices and 10 edges
d) Connected graph; 7 vertices, 7 edges
e) Tree; 5 vertices, total degree of the vertices is 10
Multiple choice question
1. A tree is
A) Any graph that is connected and every edge is a bridge.
B) Any graph that has no circuits.
C) Any graph with one component.
D) Any graph that has no bridges.
2. Graph 1 is connected and has no circuits. Graph 2 is such that for any pair of vertices in the
graph there is one and only one path joining them.
A) Graph 1 cannot be a tree; Graph 2 cannot be a tree.
B) Graph 1 must be a tree; Graph 2 may or may not be a tree.
C) Graph 1 must be a tree; Graph 2 must be a tree.
D) Graph 1 must be a tree; Graph 2 cannot be a tree.
3. Suppose T is a tree with 21 vertices. Then
A) T has one bridge.
B) T has no bridges.
C) T can have any number of bridges.
D) T has 20 bridges.
4. In a tree between every pair of vertices there is?
A) Exactly one path


B) A self-loop
C) Two circuits
D) n number of paths
5. If a tree has 8 vertices then it has
A) 6 edges
B) 7 edges
C) 9 edges
D) None of the above
6. A graph is tree if and only if
A) Is planar
B) Contains a circuit
C) Is minimally
D) Is completely connected
7. Suppose that A is an array storing n identical integer values. Which of the following sorting
algorithms has the smallest running time when given as input this array A?
A) Insertion Sort
B) Selection Sort
C) Ordered-dictionary sort implemented using an AVL tree.
D) Ordered-dictionary sort implemented using a (2,4)-tree.
8. How many different (2, 4)-trees containing the keys 1, 2, 3, 4, and 5 exist (each key must
appears once in each one of these (2, 4)-trees)?
(A) 2 (B) 3 (C) 4 (D) 5
9. For which of the following does there exist a graph G = (V, E, φ) satisfying the specified
conditions?
(A) A tree with 9 vertices and the sum of the degrees of all the vertices is 18.
(B) A graph with 5 components 12 vertices and 7 edges.
(C) A graph with 5 components 30 vertices and 24 edges.
(D) A graph with 9 vertices, 9 edges, and no cycles.
10. For which of the following does there exist a simple graph G = (V, E) satisfying the specified
conditions?
(A) It has 3 components 20 vertices and 16 edges.
(B) It has 6 vertices, 11 edges, and more than one component.
(C) It is connected and has 10 edges 5 vertices and fewer than 6 cycles.
(D) It has 7 vertices, 10 edges, and more than two components.
11. For which of the following does there exist a tree satisfying the specified constraints?
(A) A binary tree with 65 leaves and height 6.
(B) A binary tree with 33 leaves and height 5.
(C) A full binary tree with height 5 and 64 total vertices.
(D) A rooted tree of height 3, every vertex has at most 3 children. There are 40 total
vertices.
12. For which of the following does there exist a tree satisfying the specified constraints?
(A) A full binary tree with 31 leaves, each leaf of height 5.
(B) A rooted tree of height 3 where every vertex has at most 3 children and there are 41
total vertices.
(C) A full binary tree with 11 vertices and height 6.
(D) A binary tree with 2 leaves and height 100.
13. The number of simple digraphs with |V | = 3 is


(a) 29
(b) 28
(c) 27
(d) 26
14. The number of simple digraphs with |V | = 3 and exactly 3 edges is
(a) 92
(b) 88
(c) 80
(d) 84
15. The number of oriented simple graphs with |V | = 3 is
(a) 27
(b) 24
(c) 21
(d) 18
16. The number of oriented simple graphs with |V | = 4 and 2 edges is
(a) 40
(b) 50
(c) 60
(d) 70
17. Which data structure allows deleting data elements from front and inserting at rear?
(a) Stacks
(b) Queues
(c) Deques
(d) Binary search tree
18. To represent hierarchical relationship between elements, which data structure is suitable?
(a) Deque (b) Priority (c) Tree (d) All of above
19. A binary tree whose every node has either zero or two children is called
(a) Complete binary tree
(b) Binary search tree
(c) Extended binary tree
(d) None of above

20. A binary tree can easily be converted into q 2-tree
(a) by replacing each empty sub tree by a new internal node
(b) by inserting an internal nodes for non-empty node
(c) by inserting an external nodes for non-empty node
(d) by replacing each empty sub tree by a new external node

Unit – 6 : Spanning Trees
Short question answer
1. Define following.
Spanning Tree
Minimum Spanning Tree

2. Draw all the spanning trees of this graph:


3. What is the purpose of Spanning Tree Protocol in a switched LAN?
4. What is Spanning tree?
5. Justify the statement” Every connected graph has a spanning tree.”
6. Assuming that G0 has a minimum spanning T0, is it true that the number of edges in the T0 no
greater than T? Answer yes or no and your answer explain in one sentence.
7. Assuming that G’ has a minimum spanning tree T’, by how many edges can T’ differ from T.
8. How many spanning tree does the following graph have?

9. How many spanning tree does the following graph have?

10. How many spanning trees does the following graph have?

11. Is the minimum weight edge in a graph always in any minimum spanning tree for a graph? Is
it always in any single source shortest path tree for the graph? Justify your answers.
12. Draw minimum spanning tree.
13. State whether your minimum spanning tree is unique.
14. State difference between following: Spanning Tree and minimum spanning tree



Long question answer
1. Draw all the spanning trees of k_3.
2. Give the step by step procedure of prim’s algorithm to find the minimum spanning tree.
3. Give the step by step procedure of kruskal’s algorithm to find the minimum spanning tree.
4. For each of the following graphs:

(a) Find all spanning trees.
(b) Find all spanning trees up to isomorphism.
(c) Find all depth-first spanning trees rooted at A.
(d) Find all depth-first spanning trees rooted at B.
5. For each of the following graphs:

(a) Find all minimum spanning trees.
(b) Find all minimum spanning trees up to isomorphism.
(c) Among all depth-first spanning trees rooted at A, find those of minimum weight.
(d) Among all depth-first spanning trees rooted at B, find those of minimum weight.
6. In the following graph, the edges are weighted either 1, 2, 3, or 4.

Referring to discussion following of Kruskal’s algorithm:
(a) Find a minimum spanning tree using Prim’s algorithm
(b) Find a minimum spanning tree using Kruskal’s algorithm.
(c) Find a depth-first spanning tree rooted at K.
7. Let T = (V,E) be a tree and let d(v) be the degree of a vertex
(a) Prove that Pv2V (2 − d(v)) = 2.
(b) Prove that, if T has a vertex of degree m 2, then it has at least m vertices of degree 1.
(c) Give an example for all m 2 of a tree with a vertex of degree m and only m leaves.
8. Does every connected graph have a spanning tree? Either give a proof or a counter-example.
9. Give an algorithm that determines whether a graph has a spanning tree, and finds such a tree
if it exists, that takes time bounded above by a polynomial in v and e, where v is the number of
vertices, and e is the number of edges.


10. Find all spanning trees (list their edge sets) of the graph

11. Show that a finite graph is connected if and only if it has a spanning tree.
12. Find spanning tree of maximal (minimal) weights for graphs from figures using algorithms of
kruskal and prim.

13. Prove that every minimal spanning tree of a connected graph may be constructed by
kruskal’s algorithm.
14. Use Kruskal’s algorithm to find all least weight spanning trees for this weighted graph.

15. Find a minimum weight spanning tree in each of the following weighted graph

16. Find a minimum weight spanning tree in each of the following weighted graph


17. Draw all the spanning trees of K4.
18. Find the number of spanning trees in

19.
a. Use Kruskal’s algorithm to find a minimal spanning tree for the graph below.
b. Use Prim’s algorithm (as shown in class) to find a minimal spanning tree different
from the one in part

Multiple choice question
1. How many spanning trees does the following graph have?

A) 1
B) 2
C) 3
D) 4
The question(s) that follow refer to the problem of finding the minimum spanning tree for the
weighted graph shown below.


3. In Figure, using Kruskal's algorithm, which edge should we choose first?
A) AB
B) EG
C) BE
D) AG
4. In Figure, using Kruskal's algorithm, which edge should we choose third?
A) EF
B) AG
C) BG
D) EG
5. In Figure, using Kruskal's algorithm, which edge should we choose last?
A) AB
B) AC
C) CD
D) BC
6. In figure, which of the following edges of the given graph are not part of the minimum
spanning tree?
A) AC
B) EF
C) AG
D) BG
7. In Figure, the total weight of the minimum spanning tree is
A) 36.
B) 42.
C) 55.
D) 95.
8. Which of the following statements is true about Kruskal's algorithm.
A) It is an inefficient algorithm, and it never gives the minimum spanning tree.
B) It is an efficient algorithm, and it always gives the minimum spanning tree.
C) It is an efficient algorithm, but it doesn't always give the minimum spanning tree.
D) It is an inefficient algorithm, but it always gives the minimum spanning tree.
For the following question(s), refer to the digraph below.


9. In Figure, which of the following is not a path from vertex E to vertex B in the digraph?
A) E, B, C, B
B) E, D, B
C) E, A, B
D) E, A, C, B
10. The critical path algorithm is
A) An approximate and inefficient algorithm.
B) An optimal and efficient algorithm.
C) An approximate and efficient algorithm.
D) An optimal and inefficient algorithm.
11. Let w be the minimum weight among all edge weights in an undirected connected graph. Let
e be a specific edge of weight w. Which of the following is FALSE?
A) There is a minimum spanning tree containing e.
B) If e is not in a minimum spanning tree T then in the cycle formed by adding e to T, all
edges have the same weight.
C) Every minimum spanning tree has an edge of weight w.
D) e is present in every minimum spanning tree.
12. A minimal spanning tree of a graph G is....?
A) A spanning sub graph
B) A tree
C) Minimum weights
D) All of above
13. A tree having a main node, which has no predecessor is....?
A) Spanning tree
B) Rooted tree
B) Weighted tree
D) None of these
14. If a graph is a tree then
A) it has 2 spanning trees
B) it has only 1 spanning tree
C) it has 4 spanning trees
D) it has 5 spanning trees
15. Any two spanning trees for a graph
A) Does not contain same number of edges
B) Have the same degree of corresponding edges
C) contain same number of edges
D) May or may not contain same number of edges
16. A sub graph of a graph G that contains every vertex of G and is a tree is called
A) Trivial tree B) empty tree


C) Spanning tree D) Minimum Spanning tree
17. The minimum number of spanning trees in a connected graph with “n” nodes is…..
A) n-1 B) n/2
C) 2 D) 1
18. A minimal spanning tree of a graph G is
A) A spanning sub graph
B) A tree
C) Minimum weights
D) All of above


QB 060010212

Uploaded by

Copyright:

Available Formats

QB 060010212

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

QB 060010212

Uploaded by

Copyright:

Available Formats

060010212-Advanced Mathematics for Computer Application

Mr. Nikhil Choksi Page 1

Mr. Nikhil Choksi Page 2

Mr. Nikhil Choksi Page 3

Mr. Nikhil Choksi Page 4

Mr. Nikhil Choksi Page 5

Mr. Nikhil Choksi Page 6

Mr. Nikhil Choksi Page 7

Mr. Nikhil Choksi Page 8

Mr. Nikhil Choksi Page 9

Mr. Nikhil Choksi Page 10

Mr. Nikhil Choksi Page 11

Mr. Nikhil Choksi Page 12

7. Draw the graphs: K7, K1,8, K4,4,C7, W7, Q4.

Mr. Nikhil Choksi Page 13

(e) (f) (g)

(h) (i) (j) (k)

(l) (m) (n)

Multiple Choice Questions

Mr. Nikhil Choksi Page 14

Mr. Nikhil Choksi Page 15

Mr. Nikhil Choksi Page 16

Mr. Nikhil Choksi Page 17

(a) (b) (c) (d)

Mr. Nikhil Choksi Page 18

Mr. Nikhil Choksi Page 19

Mr. Nikhil Choksi Page 20

Mr. Nikhil Choksi Page 21

Mr. Nikhil Choksi Page 22

Mr. Nikhil Choksi Page 23

Mr. Nikhil Choksi Page 24

Mr. Nikhil Choksi Page 25

Mr. Nikhil Choksi Page 26

Mr. Nikhil Choksi Page 27

Mr. Nikhil Choksi Page 28

Mr. Nikhil Choksi Page 29

Mr. Nikhil Choksi Page 30

Mr. Nikhil Choksi Page 31

Mr. Nikhil Choksi Page 32

Mr. Nikhil Choksi Page 33

Mr. Nikhil Choksi Page 34

Mr. Nikhil Choksi Page 35

Mr. Nikhil Choksi Page 36

Mr. Nikhil Choksi Page 37

Mr. Nikhil Choksi Page 38

You might also like