Graph

SE Computer DM Unit - 4 Graph MCQs

Question
Correct
Id Option A Option B Option C Option D
Option
Which one of the following is the
1 example of non linear data structure Graph Binary Tree Queue Link List A
Let A be an adjacency matrix of a The number of paths of Shortest path of K Length of a Eulerian Length of a Hamiltonian
2 graph G. The ij th entry in the matrix length K from vertex Vi edges from vertex Vi to path from vertex Vi to cycle from vertex Vi to B
AK , gives to vertex Vj. vertex Vj. vertex Vj. vertex Vj.
An undirected graph G with n vertices
and e edges is represented by
4 adjacency list. What is the time O (n) O (e) O (e+n) O (e2 ) C
required to generate all the connected
components?
The maximum degree of any vertex in
5 a simple graph with n vertices is
n–1 n+1 2n–1 n A
The data structure required for Breadth
6 First Traversal on a graph is queue (LIFO) stack (FIFO) array tree A
A graph with n vertices will definitely
7 have a parallel edge or self loop if the greater than n–1 less than n(n–1) greater than n(n–1)/2 less than n2/2 A
total number of edges are
An adjacency matrix representation of
8 a graph cannot contain information of : nodes edges direction of edges parallel edges D

Page 1
Graph

A queue is a, FIFO (First In First Out) LIFO (Last In First Out)

9 Ordered array. Linear tree. A
list. list.
In Breadth First Search of Graph,
10 which of the following data structure is Stack. Queue. Linked List. None of the above. B
used?
For an undirected graph G with n
11 vertices and e edges, the sum of the ne 2n 2e en C
degrees of each vertex is
Indicate which, if any, of the following
A {1,3}B {2,4}
five graphs G = (V,E, ), |V | = 5, is n {1,2}b {1,2}c {2,3}d b {4,5}f {1,3} e {1,3} d 1 {1,}2 {2,3}3 {2,3}
12 C{1,2}D{2,3} E{3,5}F
{3,4}e {3,4}a {4,5} {2,3}c {2,4}a {4,5} 4{3,4} 5{4,5}6 {4,5}
A
isomorphic to any of the other four. t
{4,5}
A graph with V = {1, 2, 3, 4} is
described by = a {1,2} b {1,2} c {1,4}
13 d {2,3} e {3,4} f {3,4}How many 1 2 4 16 C
Hamiltonian cycles does it have?
A graph with V = {1, 2, 3, 4} is
described by = a {1,2} b {1,2} c {1,4}
d {2,3} e {3,4} f {3,4} It has weights on
14 its edges given by = a b c d e f 2 3 4 5 B
3 2 1 2 4 2 . How many minimum
spanning trees does it have?

Page 2
Graph

For which of the following does there

It has 6 vertices, 11 It is connected and has It has 7 vertices, 10
exist a simple graph G = (V,E) It has 3 components 20
16 satisfying the vertices and 16 edges.
edges, and more than 10 edges 5 vertices and edges, and more than D
one component. fewer than 6 cycles. two components.
specified conditions?
The number of simple digraphs with |V
18 | = 3 and exactly 3 edges is
92 88 80 84 D
The number of oriented simple graphs
19 with |V | = 3 is 27 24 21 18 D
The number of oriented simple graphs
20 with |V | = 4 and 2 edges is
40 50 60 70 C
Compute the total number of
bicomponents in all of the following
three simple graphs,
21 G = (V,E) with |V | = 5. For each graph 4 5 6 7 C
the edge sets are as follows:
E = {1, 2}, {2, 3}, {3, 4}, {4, 5}, {1, 3},
{1, 5}, {3, 5}
E = {1, 2},
Indicate {2, 3},
which, {3, 4},
if any, {4, 5},
of the {1, 3}
following a {1,2} b {2,3}
a {1,2} b {2,3} c {1,2} b{4,5} a {1,3} e {1,3} d b {4,5} f {1,3} e {1,3} d
22 five graphs G = (V,E, ), |V | = 5, isot c {1,2} d {2,3} e A
d {1,3} e {2,3} f {4,5}. {2,3} c {2,5} f {4,5}. {2,3} c {2,4} a {4,5}.
connected. {3,4} f {1,5} .
Indicate which, if any, of the following a {1,3} b {3,4}
five graphs G = (V,E, ), |V | = 5, have F{1,2} B {1,2} C {2,3} b {4,5} f {1,3} e {1,3} d 1 {1,2} 2 {1,2} 3 {2,3}
23 D{3,4} E {4,5} A {4,5}. {2,3} c {2,4} a {4,5}. 4 {3,4}5 {4,5} 6 {4,5}.
c{1,2} d {2,3} e D
an Eulerian circuit. {3,5} f {4,5}.
A graph is a set of vertices and a
24 a set of integers; a set of integers;
set of edges;
a set of edges; C
The degree of a vertex in a graph is the number of vertices the number of other the number of distinct
25 in its graph; vertices incident to it
the number of paths;
connected subgraphs;
B
series of edges that connect two
27 vertices is called a path; a cycle; a connection; a tree; A
To design a communications network
28 that joins all nodes without excessive path; minimal spanning three; expression tree; search tree B
lines, we must find a

Page 3
Graph

A series of edges that form a path

29 from a vertex to itself is
a spanning path; a cycle; a connection; a tree; B
A weighted graph has an adjacency
30 matrix that is
integers; vertices; real numbers and .; booleans; A
A graph may be fully represented by the degrees of its
32 its vertices; its edges; an adjacency matrix;
vertices;
C
The prerequesite relationships among
33 required courses in the Computer binary tree; linked list; directed acyclic graph; weighted graph; C
Science major form a
34 Graph path search involves finding a set of vertices; sequence of vertices; set of edges; minimal set of edges; B
Graphs for which bijections of a special
36 kind exist between their sets of vertices nested; transitive; undecidable; isomorphic D
and edges are
Graphs that have the same structure
37 are
nested; transitive; undecidable; isomorphic C
Graph isomorphism invariant having the same
38 properties include numbers of vertices satisfiability; reachability; well ordering; A
and edges;
The reflexive transitive closure of . states to states and symbols to states and strings states and symbols to none of
39 maps from states; states; to states; symbols; these
How many edges are there in an
undirected graph with two vertices of
40 degree 7, four vertices 29 30 64 24 A
of degree 5, and the remaining four
vertices of degree is 6?
Suppose v is an isolated vertex in a
42 graph, then the degree of v is:
0 1 2 3 A

Page 4
Graph

In an undirected graph the number of

43 nodes with odd degree must be Zero Odd Prime Even D
Which of the following statement is
Every graph is not its The terminal vertex of a A tree with n vertices A single vertex in graph
44 true:
own subgraph graph are of degree two. has n edges. G is a subgraph of G.
D

The length of Hamiltonian Path in a

45 connected graph of n vertices is
n–1 n n+1 n/2 A
A graph with one vertex and no edges
46 is: multigraph digraph isolated graph trivial graph D
A complete graph of n vertices should
47 have __________ edges. n-1 n n(n-1)/2 n(n+1)/2 C
A Euler graph is one in which Only two vertices are of Only two vertices are of
All the vertices are of All the vertices are of
48 odd degree and rests even degree and rests
odd degree even degree
D
are even are odd
A spanning tree of a graph is one that All the vertices of the All the edges of the Only the vertices of odd Only the vertices of
49 includes graph graph degree even degree
A
In multigraph----------------------- more than one edge
can join two vertices, parallel edges allowed
50 but no edge can join to but not selfloops
A or B None of these C
itself .
In Pseudographs----------------------- more than one edge
self loops as well as
can join two vertices,
51 but no edge can join to
parallel edges are A&B None of these B
allowed.
itself .
Simple graph ----------------------- self loops as well as no self loop and no
52 parallel edges are parallel edges are A&B None of these B
allowed. present.
How many nodes are necessary to
56 construct 8 edges in which each node 4 8 16 32 B
is of degree 2

Page 5
Graph

If in a graph each edge has a direction,

57 the graph known as ___________ directed graph simple graph weighted graph None of these A

In a graph if degree of each vertex is

58 same then the graph is known directed graph simple graph weighted graph Regular graph D
as________
G is a graph whose set of vertices is v.
If V can be partitioned into two subsets
59 V1 & V2 such that every edge of G V1∩ V2 V1∪ V2 V1∩ V2 & V1∪ V2 None of these C
joins V1 with V2 also______________

A graph with n vertices and no edge is

60 known as _________________ null graph bipartite graph simple graph None of these A
How many edges has of the K4,6 graph.
62 8 16 24 32 C
A graph G is called ______________if
63 the edges do not repeat in the path. Circuit Simple path A&B None of these B

A closed path is known as

64 __________ Circuit Simple path A&B None of these A
A path is known as ________ if every
66 edge of the graph appers exactly once Hamiltonoin Circuit Hamiltonoin path Eulerian Circuit Eulerian path D
in the path.
The circuit which contains every edge
67 of the graph exactly once is Hamiltonoin Circuit Hamiltonoin path Eulerian Circuit Eulerian path C
called___________
A circuit in a connected graph G is a
________________ if it contains every
69 vertex of G exactly once except the first
Hamiltonoin Circuit Hamiltonoin path Eulerian Circuit Eulerian path A
and the last vertex

Page 6