1. Which of the following statements for a simple graph is correct?

a) Every path is a trail

b) Every trail is a path

c) Every trail is a path, as well as every path, is a trail

d) Path and trail have no relation

Answer: a

In a walk if the vertices are distinct it is called a path, whereas if the edges are distinct it is called a trail.

2. In the given graph identify the cut vertices.

a) B and E

b) C and D

c) A and E

d) C and B

Answer: d

After removing either B or C, the graph becomes disconnected.

3. For the given graph(G), which of the following statements is true?

a) G is a complete graph

b) G is not a connected graph

c) The vertex connectivity of the graph is 2

d) The edge connectivity of the graph is 1

Answer: c

After removing vertices B and C, the graph becomes disconnected.

4. What is the number of edges present in a complete graph having n vertices?

a) (n*(n+1))/2

b) (n*(n-1))/2

c) n

d) Information given is insufficient

Answer: b

A number of ways in which every vertex can be connected to each other are nC2.

5. The given Graph is regular.

a) True

b) False

Answer: a

In a regular graph, the degrees of all the vertices are equal. In the given graph the degree of every vertex is 3.

6. In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices.

a) True

b) False

Answer: b

The sum of the degrees of the vertices is equal to twice the number of edges.

7. A connected planar graph having 6 vertices, 7 edges contains _____________ regions.

a) 15

b) 3

c) 1

d) 11

Answer: b

A connected planar graph has 6 vertices, and 7 edges containing 3 regions.

By euler’s formula the relation between vertices(n), edges(q) and regions(r) is given by n-q+r=2.

8. If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G'(Complement of G) is ___________

a) (n*n-n-2*m)/2

b) (n*n+n+2*m)/2

c) (n*n-n-2*m)/2

d) (n*n-n+2*m)/2

Answer: a

If a simple graph G, contains n vertices and m edges, the number of edges in Graph G'(Complement of G) is (n*n-n-2*m)/2.

The union of G and G’ would be a complete graph so, the number of edges in G’= number of edges in the complete form of G(nC2)-edges in G(m).

9. Which of the following properties does a simple graph not hold?

a) Must be connected

b) Must be unweighted

c) Must have no loops or multiple edges

d) Must have no multiple edges

Answer: a

- A graph is disconnected if at least two vertices of the graph are not connected by a path.
- If graph G is disconnected, then every maximal connected subgraph of G is called a connected component of graph G.
- A simple graph may be connected or disconnected.

10. What is the maximum number of edges in a bipartite graph having 10 vertices?

a) 24

b) 21

c) 25

d) 16

Answer: c

Let one set have n vertices another set would contain 10-n vertices.

A total number of edges would be n*(10-n), and differentiating with respect to n, would yield the answer.

11. Which of the following is true?

a) A graph may contain no edges and many vertices

b) A graph may contain many edges and no vertices

c) A graph may contain no edges and no vertices

d) A graph may contain no vertices and many edges

Answer: b

A graph must contain at least one vertex.

12. For a given graph G having v vertices and e edges which is connected and has no cycles, which of the following statements is true?

a) v=e

b) v = e+1

c) v + 1 = e

d) v = e-1

Answer: b

For a given graph G having v vertices and e edges which is connected and has no cycles, the v = e+1 equation holds true.

13. For which of the following combinations of the degrees of vertices would the connected graph be eulerian?

a) 1,2,3

b) 2,3,4

c) 2,4,5

d) 1,3,5

Answer: a

1,2,3 combination of the degrees of vertices would the connected graph be eulerian, A graph is eulerian if either all of its vertices are even or if only two of its vertices are odd.

14. A graph with all vertices having an equal degree is known as a __________

a) Multi Graph

b) Regular Graph

c) Simple Graph

d) Complete Graph

Answer: b

A graph with all vertices having an equal degree is known as a Regular Graph. n graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency.

15. Which of the following ways can be used to represent a graph?

a) Adjacency List and Adjacency Matrix

b) Incidence Matrix

c) Adjacency List, Adjacency Matrix as well as Incidence Matrix

d) No way to represent

Answer: c

Adjacency Matrix, Adjacency List, and Incidence Matrix are used to represent a graph.

1. The number of elements in the adjacency matrix of a graph having 7 vertices is __________

a) 7

b) 14

c) 36

d) 49

Answer: d

There are n*n elements in the adjacency matrix of a graph with n vertices.

The number of elements in the adjacency matrix of a graph having 7 vertices is 7 × 7 = 49.

2. What would be the number of zeros in the adjacency matrix of the given graph?

a) 10

b) 6

c) 16

d) 0

Answer: b

A total number of values in the matrix is 4*4=16, out of which 6 entries are non-zero.

3. Adjacency matrix of all graphs is symmetric.

a) False

b) True

Answer: a

The adjacency matrix of all graphs is symmetric. Only undirected graphs produce symmetric adjacency matrices. An adjacency matrix is a way of representing a graph as a matrix of booleans (0’s and 1’s).

4. The time complexity to calculate the number of edges in a graph whose information is stored in form of an adjacency matrix is _________

a) O(V)

b) O(E2)

c) O(E)

d) O(V^{2})

Answer: d

The time complexity to calculate the number of edges in a graph whose information is stored in form of an adjacency matrix is O(V^{2}).

As V entries are 0, a total of V^{2}-V entries are to be examined.

5. For the adjacency matrix of a directed graph the row sum is the _________ degree and the column sum is the ________ degree.

a) in, out

b) out, in

c) in, total

d) total, out

Answer: b

For the adjacency matrix of a directed graph, the row sum is the out degree and the column sum is the in degree.

The row number of the matrix represents the tail, while the Column number represents the head of the edge.

6. What is the maximum number of possible non zero values in an adjacency matrix of a simple graph with n vertices?

a) (n*(n-1))/2

b) (n*(n+1))/2

c) n*(n-1)

d) n*(n+1)

Answer: c

The maximum number of possible non-zero values in an adjacency matrix of a simple graph with n vertices is n*(n-1).

Out of n*n possible values for a simple graph, the diagonal values will always be zero.

7. On which of the following statements does the time complexity of checking if an edge exists between two particular vertices not, depend?

a) Depends on the number of edges

b) Depends on the number of vertices

c) Is independent of both the number of edges and vertices

d) It depends on both the number of edges and vertices

Answer: c

To check if there is an edge between to vertices i and j, it is enough to see if the value of A[i][j] is 1 or 0, here A is the adjacency matrix.

8. In the given connected graph G, what is the value of rad(G) and diam(G)?

a) 2, 3

b) 3, 2

c) 2, 2

d) 3, 3

Answer: a

In the given connected graph G, the value of eccentricity for vertices A and C is 2 whereas for F, B, D, and E it is 3.

9. Which of these adjacency matrices represents a simple graph?

a) [ [1, 0, 0], [0, 1, 0], [0, 1, 1] ]

b) [ [1, 1, 1], [1, 1, 1], [1, 1, 1] ]

c) [ [0, 0, 1], [0, 0, 0], [0, 0, 1] ]

d) [ [0, 0, 1], [1, 0, 1], [1, 0, 0] ]

Answer: d

[ [0, 0, 1], [1, 0, 1], [1, 0, 0] ] adjacency matrices represents a simple graph. A simple graph must have no self-loops and should be undirected.

10. Given an adjacency matrix A = [ [0, 1, 1], [1, 0, 1], [1, 1, 0] ], The total no. of ways in which every vertex can walk to itself using 2 edges is ________

a) 2

b) 4

c) 6

d) 8

Answer: c

Given an adjacency matrix A = [ [0, 1, 1], [1, 0, 1], [1, 1, 0] ], The total no. of ways in which every vertex can walk to itself using 2 edges is 6.

A2 = [ [2, 1, 1], [1, 2, 1], [1, 1, 2] ], all the 3 vertices can reach to themselves in 2 ways, hence a total of 3*2, 6 ways.

11. If A[x+3][y+5] represents an adjacency matrix, which of these could be the value of x and y.

a) x=5, y=3

b) x=3, y=5

c) x=3, y=3

d) x=5, y=5

Answer: a

All adjacency matrices are square matrices.

12. Two directed graphs(G and H) are isomorphic if and only if A=PBP-1, where P and A are adjacency matrices of G and H respectively.

a) True

b) False

Answer: a

Two directed graphs(G and H) are isomorphic if and only if A=PBP-1. This is a property of isomorphic graphs.

where P and A are adjacency matrices of G and H respectively.

1. Incidence matrix and Adjacency matrix of a graph will always have the same dimensions?

a) True

b) False

Answer: b

For a graph having V vertices and E edges, the Adjacency matrix has V*V elements while the Incidence matrix has V*E elements.

2. The column sum in an incidence matrix for a simple graph is __________

a) depends on the number of edges

b) always greater than 2

c) equal to 2

d) equal to the number of edges

Answer: c

The column sum in an incidence matrix for a simple graph is equal to 2. For every edge, only the vertices with which it is connected would have the value 1 in the matrix, as an edge connects two vertices sum will always be 2.

3. What are the dimensions of an incidence matrix?

a) Number of edges*number of edges

b) Number of edges*number of vertices

c) Number of vertices*number of vertices

d) Number of edges * (1⁄2 * number of vertices)

Answer: b

The dimensions of an incidence matrix are Number of edges*number of vertices

Columns may represent edges and vertices may be represented by the rows.

4. The column sum in an incidence matrix for a directed graph having no self-loop is __________

a) 0

b) 1

c) 2

d) equal to the number of edges

Answer: a

The column sum in an incidence matrix for a directed graph having no self-loop is 0.

Under every edge column, there would be either all 0 values or a pair of -1 and +1 values that exist.

5. Time complexity to check if an edge exists between two vertices would be ___________

a) O(V*V)

b) O(V+E)

c) O(1)

d) O(E)

Answer: d

The time complexity to check if an edge exists between two vertices would be O(E).

We have to check for all edges, in the worst case, the vertices will have no common edge.

7. If a connected Graph (G) contains n vertices what would be the rank of its incidence matrix?

a) n-1

b) values greater than n are possible

c) values less than n-1 are possible

d) insufficient Information is given

Answer: a

If a connected Graph (G) contains n vertices n-1 is the rank of its incidence matrix.

Every column of the incidence matrix may contain only +1 and -1 as non-zero entries rank would be less than n.

8. In the following DAG find out the number of required Stacks in order to represent it in a Graph Structured Stack.

a) 1

b) 2

c) 3

d) 4

Answer: c

The number of required Stacks in order to represent it in a Graph Structured Stack is 3. Path ADE, BDE, and BCE are possible.

9. A Graph Structured Stack is a ________

a) Undirected Graph

b) Directed Graph

c) Directed Acyclic Graph

d) Regular Graph

Answer: c

A Graph Structured Stack is a Directed Acyclic Graph with each path representing a stack.

10. If a Graph Structured Stack contains {1,2,3,4} {1,5,3,4} {1,6,7,4} and {8,9,7,4}, what would be the source and sink vertices of the DAC?

a) Source – 1, 8 Sink – 7,4

b) Source – 1 Sink – 8,4

c) Source – 1, 8 Sink – 4

d) Source – 4, Sink – 1,8

Answer: c

If a Graph Structured Stack contains {1,2,3,4} {1,5,3,4} {1,6,7,4} and {8,9,7,4}. Then the source and sink vertices of the DAC 1,8 and 4 respectively.

Every Stack of the Graph Structured Stack represents a path, each path starts with the source vertex and ends with the sink vertex.

11. Graph Structured Stack finds its application in _____________

a) Bogo Sort

b) Tomita’s Algorithm

c) Todd–Coxeter algorithm

d) Heap Sort

Answer: b

Graph Structured Stack finds its application in Tomita’s Algorithm.

Tomita’s is a parsing algorithm that uses Graph Structured Stack in its implementation.

12. If in a DAG N sink vertices and M source vertices exists, then the number of possible stacks in the Graph Structured Stack representation would come out to be N*M.

a) True

b) False

Answer: b

The answer would depend on the intermediate vertices also.

1. Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is ___________

a) O(E)

b) O(V*V)

c) O(E+V)

d) O(V)

Answer: c

Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is O(E+V).

In an adjacency list for every vertex, there is a linked list that has the values of the edges to which it is connected.

2. For some sparse graphs an adjacency list is more space-efficient than an adjacency matrix.

a) True

b) False

Answer: a

Space complexity for adjacency matrix is always O(V*V) while space complexity for adjacency list, in this case, would be O(V).

3. Time complexity to find if there is an edge between 2 particular vertices is _________

a) O(V)

b) O(E)

c) O(1)

d) O(V+E)

Answer: a

The time complexity to find if there is an edge between 2 particular vertices is O(V). The maximum edge a vertex can have is V-1.

4. For the given conditions, which of the following is in the correct order of increasing space requirement?

i) Directed, no weight

ii) Directed, weighted

iii) Undirected, weighted

iv) All of the above

a) ii iii i iv

b) i iii ii iv

c) iv iii i ii

d) i ii iii iv

Answer: a

The correct order of increasing space requirements is

i) Directed, no weight

ii) Directed, weighted

iii) Undirected, weighted

i) takes v+4e, ii) takes v+2e, iii) takes v+3e, iv) takes v +6e space.

5. Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is __________

a) O(V)

b) O(E*E)

c) O(E)

d) O(E+V)

Answer: c

Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is O(E).

In an adjacency list for every vertex, there is a linked list that has the values of the edges to which it is connected.

7. In which case adjacency list is preferred in front of an adjacency matrix?

a) Dense graph

b) Sparse graph

c) Adjacency list is always preferred

d) Complete graph

Answer: b

In the case of a sparse graph, most of the entries in the adjacency matrix would be 0, hence adjacency list would be preferred.

8. To create an adjacency list C++’s map container can be used.

a) True

b) False

Answer: a

We can create a mapping from a string to a vector, where the string would be the name of the vertex and the vector would contain the name of the vertices to which it is connected.

9. What would be the time complexity of the following function which adds an edge between two vertices i and j, with some weight ‘weigh’ to the graph having V vertices?

vector<int> adjacent[15] ; vector<int> weight[15]; void addEdge(int i,int j,int weigh) { adjacent[a].push_back(i); adjacent[b].push_back(j); weight[a].push_back(weigh); weight[b].push_back(weigh); }

a) O(1)

b) O(V)

c) O(V*V)

d) O(log V)

Answer: a

The time complexity of the following function which adds an edge between two vertices i and j, with some weight ‘weigh’ to the graph having V vertices is O(1).

The function win in the constant time as all the four-step takes constant time.

10. What would be the time complexity of the BFS traversal of a graph with n vertices and n1.25 edges?

a) O(n)

b) O(n^{1.25})

c) O(n^{2.25})

d) O(n*n)

Answer: b

The time complexity of the BFS traversal of a graph with n vertices and n1.25 edges is O(n^{1.25}).

The time complexity for BFS is O(|V| + |E|) = O(n + n1.25) = O(n^{1.25}).

1. The number of possible undirected graphs which may have self-loops but no multiple edges and have n vertices is ________

a) 2^{((n*(n-1))/2)}

b) 2^{((n*(n+1))/2)}

c) 2^{((n-1)*(n-1))/2)}

d) 2^{((n*n)/2)}

Answer: d

The number of possible undirected graphs which may have self-loops but no multiple edges and have n vertices is 2^{((n*n)/2)}.

There can be at most, n*n edges in an undirected graph.

2. Given a plane graph, G has 2 connected components, having 6 vertices, 7 edges, and 4 regions. What will be the number of connected components?

a) 1

b) 2

c) 3

d) 4

Answer: b

Euler’s Identity says V – E + R = 1+ number of connected components. The number of connected components

6 − 7 + 4 = 1 + 2 = 2

3. Number of vertices with odd degrees in a graph having an eulerian walk is ________

a) 0

b) Can’t be predicted

c) 2

d) either 0 or 2

Answer: d

Number of vertices with odd degrees in a graph having an eulerian walk is either 0 or 2.

If the start and end vertices for the path are the same the answer would be 0 otherwise 2.

5. All paths and cyclic graphs are bipartite graphs.

a) True

b) False

Answer: b

Only paths and even cycles are bipartite graphs. A bipartite graph (or digraph) is a graph whose vertices can be divided into two disjoint and independent sets, that is every edge connects a vertex into one.

6. What is the number of vertices of degree 2 in a path graph having n vertices, here n>2.

a) n-2

b) n

c) 2

d) 0

Answer: a

The number of vertices of degree 2 in a path graph having n vertices is n-2. Only the first and the last vertex would have degree 1, others would be of degree 2.

7. All trees with n vertices consist of n-1 edges.

a) True

b) False

Answer: a

A tree is acyclic in nature. All trees with n vertices consist of n-1 edges.

9. In the given graph which edge should be removed to make it a Bipartite Graph?

a) A-C

b) B-E

c) C-D

d) D-E

Answer: a

The resultant graph would be a Bipartite Graph having {A, C, E} and {D, B} as its subgroups.

10. What would the time complexity be to check if an undirected graph with V vertices and E edges is Bipartite or not given its adjacency matrix?

a) O(E*E)

b) O(V*V)

c) O(E)

d) O(V)

Answer: b

O(V*V) is the time complexity be to check if an undirected graph with V vertices and E edges is Bipartite or not given its adjacency matrix.

A graph can be checked for being Bipartite by seeing if it is 2-colorable or not, which can be obtained with the help of BFS.

1. Dijkstra’s Algorithm will work for both negative and positive weights?

a) True

b) False

Answer: b

Dijkstra’s Algorithm assumes all weights to be non-negative. Dijkstra’s algorithm is widely used in the routing protocols required by the routers to update their forwarding table.

2. A graph having an edge from each vertex to every other vertex is called a ___________

a) Tightly Connected

b) Strongly Connected

c) Weakly Connected

d) Loosely Connected

Answer: a

A graph having an edge from each vertex to every other vertex is called a Tightly Connected. This is a part of the nomenclature followed in Graph Theory.

3. What is the number of an unlabeled simple directed graph that can be made with 1 or 2 vertices?

a) 2

b) 4

c) 5

d) 9

Answer: b

The number of an unlabeled simple directed graph that can be made with 1 or 2 vertices are 4.

4. Floyd Warshall Algorithm used to solve the shortest path problem has a time complexity of __________

a) O(V*V)

b) O(V*V*V)

c) O(E*V)

d) O(E*E)

Answer: b

Floyd Warshall Algorithm used to solve the shortest path problem has a time complexity of O(V*V*V).

The Algorithm uses Dynamic Programming and checks for every possible path.

5. All Graphs have a unique representation on paper.

a) True

b) False

Answer: b

The same Graph may be drawn in different ways on paper.

6. Assuming the value of every weight to be greater than 10, in which of the following cases the shortest path of a directed weighted graph from 2 vertices u and v will never change?

a) add all values by 10

b) subtract 10 from all the values

c) multiply all values by 10

d) in both the cases of multiplying and adding by 10

Answer: c

In the case of addition or subtraction, the shortest path may change because the number of edges between different paths may be different, while in the case of multiplication path won’t change.

7. What is the maximum possible number of edges in a directed graph with no self-loops having 8 vertices?

a) 28

b) 64

c) 256

d) 56

Answer: d

If a graph has V vertices then every vertex can be connected to a possible of V(V-1) vertices.

The maximum possible number of edges in a directed graph with no self-loops having 8 vertices is 56.

8. What would be the DFS traversal of the given Graph?

a) ABCED

b) AEDCB

c) EDCBA

d) ADECB

Answer: a

The DFS traversal of the given Graph is ABCED

In this case, two answers are possible including ABC.

10. What is the maximum number of edges present in a simple directed graph with 7 vertices if there exist no cycles in the graph?

a) 21

b) 7

c) 6

d) 49

Answer: c

If no cycles exist then the difference between the number of vertices and edges is 1.

The maximum number of edges present in a simple directed graph with 7 vertices if there exist no cycles in the graph is 6.

1. Every Directed Acyclic Graph has at least one sink vertex.

a) True

b) False

Answer: a

A sink vertex is a vertex that has an outgoing degree of zero.

2. Which of the following is not a topological sorting of the given graph?

a) A B C D E F

b) A B F E D C

c) A B E C F D

d) A B C D F E

Answer: d

Topological sorting is a linear arrangement of vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. In A B C D F E, F comes before E in order.

3. With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess?

a) (V*(V-1))/2

b) (V*(V+1))/2

c) (V+1)C2

d) (V-1)C2

Answer: a

The first edge would have an outgoing degree of almost V-1, the next edge would have V-2 and so on, hence V-1 + V-2…. +1 equals (V*(V-1))/2.

4. The topological sorting of any DAG can be done in ________ time.

a) cubic

b) quadratic

c) linear

d) logarithmic

Answer: c

The topological sorting of any DAG can be done in linear time.

Topological sorting can be done in O(V+E),

here V and E represent a number of vertices and the number of edges respectively.

5. If there are more than 1 topological sorting of a DAG is possible, which of the following is true.

a) Many Hamiltonian paths are possible

b) No Hamiltonian path is possible

c) Exactly 1 Hamiltonian path is possible

d) Given information is insufficient to comment anything

Answer: b

If there are more than 1 topological sorting of a DAG is possible, then No Hamiltonian path is possible.

For a Hamiltonian path to exist all the vertices must be connected with a path, had that happened there would have been a unique topological sort.

6. What sequence would the BFS traversal of the given graph yield?

a) A F D B C E

b) C B A F E D

c) A B D C E F

d) E F D C B A

Answer: c

In BFS nodes get explored and then the neighbors of the current node get explored, before moving on to the next levels.

The sequence of the BFS traversal of the given graph yield is A B D C E F.

1. In which of the following does a Directed Acyclic Word Graph finds its application in?

a) String Matching

b) Number Sorting

c) Manipulations on numbers

d) Pattern Printing

Answer: a

A Directed Acyclic Word Graph finds its application in String Matching.

A Directed Acyclic Word Graph is similar to a suffix tree, it can be viewed as a Deterministic Finite Automata.

2. What is the number of words that can be formed from the given Directed Acyclic Word Graph?

a) 2

b) 4

c) 12

d) 7

Answer: b

The number of words that can be formed from the given Directed Acyclic Word Graph is 2.

Words namely BATS, BOTS, BAT, and BOT can be formed.

3. Determine the longest string which is described by the given Directed Acyclic Word Graph.

a) BATS

b) BOATS

c) BOT

d) BAT

Answer: a

Starting from the initial state and choosing B, A, T, and S respectively.

4. What is the time complexity to check if a string(length S1) is a substring of another string(length S2) stored in a Directed Acyclic Word Graph, given that S2 is greater than S1?

a) O(S1)

b) O(S2)

c) O(S1+S2)

d) O(1)

Answer: a

The time complexity to check if a string(length S1) is a substring of another string(length S2) stored in a Directed Acyclic Word Graph is O(S1). For each check of a word of length S1, we need to follow at most S1 edges.

5. In which of the following case does a Propositional Directed Acyclic Graph is used for?

a) Representation of Boolean Functions

b) String Matching

c) Searching

d) Sorting of number

Answer: a

A Propositional Directed Acyclic Graph is used to represent a boolean function.

6. Consider the following symbols and choose which of the symbols represent nodes having at least one child?

i) Δ ii) ◊ iii) ∇ iv) T v) ⊥

a) iv) and v)

b) iii) iv) and v)

c) i) and ii)

d) i) and iii)

Answer: c

The symbols Δ and ◊ represents logical AND and OR gates.

7. Which of the following symbols represent nodes having exactly one child?

i) Δ ii) ◊ iii) ∇ iv) T v) ⊥

a) iv) and v)

b) v)

c) i) and iii)

d) iii)

Answer: d

∇ the symbol represents the logical NOT gate.

8. Which of the following symbols represent leaf nodes?

i) Δ ii) ◊ iii) ∇ iv) T v) ⊥

a) iv) and v)

b) v)

c) i) and iii)

d) ii)

Answer: a

The two symbols T, ⊥ represent the Boolean values.

9. Every Binary Decision Diagram is also a Propositional Directed Acyclic Graph.

a) True

b) False

Answer: a

Both Binary Decision Diagram and Propositional Directed Acyclic Graph may be used to represent the same Boolean function.

10. In a Propositional Directed Acyclic Graph Leaves may be labeled with a boolean variable.

a) True

b) False

Answer: a

In a Propositional Directed Acyclic Graph leaves maybe labeled with a boolean variable, T or ⊥.

1. Given Adjacency matrices determine which of them are PseudoGraphs?

i) {{1,0} {0,1}}

ii) {{0,1}{1,0}}

iii) {{0,0,1}{0,1,0}{1,0,0}}

iv) Both i and iii

Answer: d

{{1,0} {0,1}} and {{0,0,1}{0,1,0}{1,0,0}} matrices determine which of them are PseudoGraphs.

In {{1,0} {0,1}} self-loops exist for both the vertices and in {{0,0,1}{0,1,0}{1,0,0}} self-loop exist for the second vertex.

2. All undirected Multigraphs contain eulerian cycles.

a) True

b) False

Answer: a

All undirected Multigraphs contain eulerian cycles. Only graphs with every vertex having an even degree have eulerian circuits or cycles.

3. Determine the number of vertices for the given Graph or Multigraph?

G is a 4-regular Graph having 12 edges.

a) 3

b) 6

c) 4

d) Information given is insufficient

Answer: b

The Sum of degrees of all the edges is equal to 2 times the number of edges. 2*12=4*n, n=>6.

4. Which of the following statement is true.

a) There exists a Simple Graph having 10 vertices such that the minimum degree of the graph is 0 and the maximum degree is 9

b) There exists a MultiGraph having 10 vertices such that the minimum degree of the graph is 0 and the maximum degree is 9

c) There exists a MultiGraph as well as a Simple Graph having 10 vertices such that the minimum degree of the graph is 0 and the maximum degree is 9

d) None of the mentioned

Answer: b

If a vertex has a degree of 9 that means it is connected to all the other vertices, in the case of Multigraphs for an isolated vertex, multiple edges may compensate.

5. Given Adjacency matrices determine which of them are PseudoGraphs?

i) {{1,0} {0,1}}

ii) {{0,1}{1,0}}

iii) {{0,0,1}{0,1,0}{1,0,0}}

a) only i)

b) ii) and iii)

c) i) and iii)

d) i) ii) and iii)

Answer: c

In i) self-loops exist for both the vertices and in iii) self-loop exist for the second vertex.

6. A Possible number of labeled simple Directed, Pseudo, and Multigarphs exist having 2 vertices?

a) 3, Infinite, 4

b) 4, 3, Infinite

c) 4, Infinite, infinite

d) 4, Infinite, Infinite

Answer: d

MultiGraphs and PseudoGraphs may have an infinite number of edges, while 4 possible simple graphs exist.

7. Which of the following is a HyperGraph, where V is the set of vertices, E is the set of edges?

a) V = {v1, v2, v3} E = {e1, e2} = {{v2, v3} {v1, v3}}

b) V = {v1, v2} E = {e1} = {{v1, v2}}

c) V = {v1, v2, v3} E = {e1, e2, e3} = {{v2, v3}{v3, v1}{v2, v1}}

d) All of the mentioned

Answer: d

In a uniform Graph, all the hyper-edges have the same cardinality such as

a) V = {v1, v2, v3} E = {e1, e2} = {{v2, v3} {v1, v3}}

b) V = {v1, v2} E = {e1} = {{v1, v2}}

c) V = {v1, v2, v3} E = {e1, e2, e3} = {{v2, v3}{v3, v1}{v2, v1}}

8. What would be the Incidence Matrix of the given HyperGraph?

V = {x,y,z} E = {{x,y}{y}{x,z}{z,y}}

a) {{1,0,1,0},

{1,1,0,1},

{0,0,1,1}}

b) {{1,1,0,0},

{0,1,0,0},

{1,1,1,0}}

c) {{0,1,0,1},

{0,0,1,0},

{1,1,0,0}}

d) None of the Mentioned

Answer: a

The Incidence Matrix of the V = {x,y,z} E = {{x,y}{y}{x,z}{z,y}} HyperGraph is {{1,0,1,0},

{1,1,0,1},

{0,0,1,1}}

The columns represent edges while rows represent vertices.

9. What is the degree sequence of the given HyperGraph, in non-increasing order.

V = {v1,v2,v3,v4,v5,v6} E = {{v1,v4,v5} {v2,v3,v4,v5} {v2} {v1} {v1,v6}}

a) 3,2,1,1,1,1

b) 3,2,2,2,1,1

c) 3,2,2,2,2,1

d) 3,2,2,1,1,1

Answer: b

The degree sequence of the given HyperGraph, in non-increasing order of v1,v2,v3,v4,v5,v6 is 3,2,1,2,2,1 respectively.

10. MultiGraphs having self-loops are called PseudoGraphs?

a) True

b) False

Answer: a

All PsuedoGraphs are MultiGraphs, but all MultiGraphs are not PseudoGraphs as all PseudoGraphs have a self-loop, but all MultiGraphs do not have self-loops.

1. Binary Decision Diagram is a type of __________

a) Multigraph

b) Cyclic Graph

c) Directed Acyclic Graph

d) Directed Acyclic Word Graph

Answer: c

An Inverter is a directed graph that is used to solve Boolean expressions, hence having no loops.

2. In which of the following case does a Binary Decision Diagram is used for?

a) Representation of Boolean Functions

b) String Matching

c) Searching

d) Sorting of number

Answer: a

A binary decision diagram is a rooted, directed, acyclic graph. A Binary Decision Diagram is used to represent a Boolean function.

3. In a Binary Decision Diagram, how many types of terminal exists?

a) 1

b) 2

c) 3

d) 4

Answer: b

A binary decision diagram is a rooted, directed, acyclic graph. A Binary Decision Diagram is used to represent a Boolean function. In a BDD, 2 terminals namely terminal-0 and terminal-1 exist.

4. In a Binary Decision Diagrams 0 values by a _________ line and the 1 values are represented by a _________ line.

a) dashed, bold

b) bold, dashed

c) dotted, bold

d) dotted, dashed

Answer: c

In a Binary Decision Diagrams 0 values by a dotted line and the 1 values are represented by a bold line.

It is used to distinguish between the 2 values without explicitly writing.

5. How many nodes are required to create a Binary Decision Tree having 4 variables?

a) 2^{4}

b) 2^{4-1}

c) 2^{5}

d) 2^{5-1}

Answer: d

2^{5-1} node is required to create a Binary Decision Tree having 4 variables.

Binary Decision Trees are complete Binary Trees of level V + 1

where

V is the number of variables.

6. Two or more Inverter Graphs can represent the same function.

a) True

b) False

Answer: a

Two or more Inverter Graphs can represent the same function. And Inverter Graphs are not canonical in nature.

7. Size of an And Inverter Graph is the number of _______ gates and the number of logic levels is a number of ________ gates on the __________ path from a primary input to a primary output.

a) AND, AND, average

b) AND, OR, longest

c) OR, OR, shortest

d) AND, AND, longest

Answer: d

Size of an And Inverter Graph is the number of AND gates and the number of logic levels is a number of AND gates on the longest path from a primary input to a primary output.

The given statement forms the attributes of the And Inverter Graph.

8. And Inverter Graph is a type of __________

a) Multigraph

b) Cyclic Graph

c) Directed Acyclic Graph

d) Directed Acyclic Word Graph

Answer: c

And Inverter Graph is a type of directed Acyclic graph that is used to solve boolean expressions, hence has no loops.

9. The And Inverter Graph representation of a Boolean function is more efficient than the Binary Decision Diagram.

a) True

b) False

Answer: a

The conversion from the network logic is faster and more scalable than in the case of the Binary Decision Diagram.

10. Which of the following logical operation can’t be implemented by polynomial-time graph manipulation algorithms using Binary Decision Diagrams?

a) Conjunction

b) Disjunction

c) Negation

d) Tautology Checking

Answer: d

In Binary Decision Diagram, Conjunction, Disjunction, Negotiation can be implemented in polynomial time whereas tautology checking can be implemented in linear time.