How many edges are there in a complete graph of order 9?
1.35
2.36
3.45
4.19
Posted Date:-2022-05-13 09:34:42
A binary cycle space forms a ______ over the two element field.
1.triangular graph
2.vector space
3. binary tree
4.hamiltonian graph
Posted Date:-2022-05-13 09:29:29
A bridge can not be a part of _______
1.a simple cycle
2.a tree
3.a clique with size ≥ 3 whose every edge is a bridge
4.a graph which contains cycles
Posted Date:-2022-05-13 09:36:54
A cycle on n vertices is isomorphic to its complement. What is the value of n?
1.5
2.32
3.17
4.8
Posted Date:-2022-05-13 09:48:42
A graph G has the degree of each vertex is ≥ 3 say, deg(V) ≥ 3 ∀ V ∈ G such that 3|V| ≤ 2|E| and 3|R| ≤ 2|E|, then the graph is said to be ________ (R denotes region in the graph)
1.Planner graph
2.Polyhedral graph
3.Homomorphic graph
4.Isomorphic graph
Posted Date:-2022-05-13 09:50:22
A graph which consists of disjoint union of trees is called ______
1.bipartite graph
2.forest
3.caterpillar tree
4.labeled tree
Posted Date:-2022-05-13 09:27:02
A graph which has the same number of edges as its complement must have number of vertices congruent to ______ or _______ modulo 4(for integral values of number of edges).
1.6k, 6k-1
2.4k, 4k+1
3.k, k+2
4. 2k+1, k
Posted Date:-2022-05-13 09:47:15
A linear graph consists of vertices arranged in a line.
1.false
2.true
3.either true or false
4.cannot determined
Posted Date:-2022-05-13 09:24:29
A polytree is called _______________
1.directed acyclic graph
2.directed cyclic graph
3.bipartite graph
4.connected graph
Posted Date:-2022-05-13 09:23:12
A trail in a graph can be described as ______________
1.a walk without repeated edges
2.a cycle with repeated edges
3.a walk with repeated edges
4.a line graph with one or more vertices
Posted Date:-2022-05-13 09:56:00
A ______ in a graph G is a circuit which consists of every vertex (except first/last vertex) of G exactly once.
1.Euler path
2.Hamiltonian path
3.Planar graph
4.Path complement graph
Posted Date:-2022-05-13 09:55:19
A _______ is a graph with no homomorphism to any proper subgraph.
1.poset
2.core
3.walk
4.trail
Posted Date:-2022-05-13 09:52:31
Any subset of edges that connects all the vertices and has minimum total weight, if all the edge weights of an undirected graph are positive is called _______
1.subgraph
2.tree
3.hamiltonian cycle
4.grid
Posted Date:-2022-05-13 09:38:05
Determine the edge count of a path complement graph with 14 vertices.
1.502
2.345
3.78
4.69
Posted Date:-2022-05-13 09:57:14
Every Isomorphic graph must have ________ representation.
1.cyclic
2.adjacency list
3.tree
4.adjacency matrix
Posted Date:-2022-05-13 09:47:58
G is a simple undirected graph and some vertices of G are of odd degree. Add a node n to G and make it adjacent to each odd degree vertex of G. The resultant graph is ______
1.Complete bipartite graph
2.Hamiltonian cycle
3.Regular graph
4.Euler graph
Posted Date:-2022-05-13 09:40:10
How many cycles are there in a wheel graph of order 5?
1.6
2.10
3.25
4.7
Posted Date:-2022-05-13 09:35:18
How many perfect matchings are there in a complete graph of 10 vertices?
1.60
2.945
3.756
4.127
Posted Date:-2022-05-13 09:49:15
If G is a simple graph with n-vertices and n>=3, the condition for G has a Hamiltonian circuit is __________
1.the degree of each vertex is at most n/2
2.the degree of each vertex is equal to n
3.the degree of every vertex is at least n+1/2
4.the degree of every vertex in G is at least n/2
Posted Date:-2022-05-13 09:30:23
If there are more than 1 topological sorting of a DAG is possible, which of the following is true.
1.Many Hamiltonian paths are possible
2.No Hamiltonian path is possible
3.Exactly 1 Hamiltonian path is possible
4.Given information is insufficient to comment anything
Posted Date:-2022-05-13 10:01:56
If two cycle graphs Gm and Gn are joined together with a vertex, the number of spanning trees in the new graph is ______
1.m+n-1
2.m-n
3.m*n
4.m*n+1
Posted Date:-2022-05-13 09:28:46
In a directed weighted graph, if the weight of every edge is decreased by 10 units, does any change occur to the shortest path in the modified graph?
1.209
2.65
3.57
4.43
Posted Date:-2022-05-13 09:58:31
In which of the following case does a Propositional Directed Acyclic Graph is used for?
1.Representation of Boolean Functions
2.String Matching
3.Searching
4.Sorting of number
Posted Date:-2022-05-13 10:08:44
In which of the following does a Directed Acyclic Word Graph finds its application in?
1.String Matching
2.Number Sorting
3.Manipulations on numbers
4.Pattern Printing
Posted Date:-2022-05-13 10:06:11
Let a graph can be denoted as ncfkedn a kind of ____________
1.cycle graph
2. line graph
3.hamiltonian graph
4.path graph
Posted Date:-2022-05-13 09:56:36
Let G be a directed graph whose vertex set is the set of numbers from 1 to 50. There is an edge from a vertex i to a vertex j if and only if either j = i + 1 or j = 3i. Calculate the minimum number of edges in a path in G from vertex 1 to vertex 50.
1.98
2.13
3.6
4.34
Posted Date:-2022-05-13 09:41:03
Let G be an arbitrary graph with v nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie down between _____ and _____
1.n-1 and n+1
2.v and k
3.k+1 and v-k
4.k-1 and v-1
Posted Date:-2022-05-13 09:44:01
Let G(V, E) be a directed graph where every edge has weight as either 1, 2 or 5, what is the algorithm used for the shortest path from a given source vertex to a given destination vertex to get the time complexity of O(V+E)?
1.BFS
2.DFS
3.Binary search
4.Radix sort
Posted Date:-2022-05-13 09:59:24
The maximum number of edges in a 8-node undirected graph without self loops is ____________
1.45
2.61
3.28
4.17
Posted Date:-2022-05-13 09:43:18
The minimum number of edges in a connected cyclic graph on n vertices is _____________
1.n – 1
2.n
3.2n+3
4.n+1
Posted Date:-2022-05-13 09:42:38
The sum of an n-node graph and its complement graph produces a graph called _______
1.complete graph
2.bipartite graph
3.star graph
4.path-complement graph
Posted Date:-2022-05-13 09:57:52
The topological sorting of any DAG can be done in ________ time.
1.cubic
2.quadratic
3.linear
4.logarithmic
Posted Date:-2022-05-13 10:01:00
The tree elements are called __________
1.vertices
2.nodes
3.points
4.edges
Posted Date:-2022-05-13 09:23:44
The _______ of a graph G consists of all vertices and edges of G.
1.edge graph
2.line graph
3.path complement graph
4.eulerian circuit
Posted Date:-2022-05-13 09:54:43
Topological sorting of a graph represents _______ of a graph.
1.linear probing
2.linear ordering
3.quadrilateral ordering
4.insertion sorting
Posted Date:-2022-05-13 09:36:07
Two labeled trees are isomorphic if ____________
1.graphs of the two trees are isomorphic
2.the two trees have same label
3.graphs of the two trees are isomorphic and the two trees have the same label
4.graphs of the two trees are cyclic
Posted Date:-2022-05-13 09:25:54
What is a bipartite graph?
1.a graph which contains only one cycle
2.a graph which consists of more than 3 number of vertices
3.a graph which has odd number of vertices and even number of edges
4.a graph which contains no cycles of odd length
Posted Date:-2022-05-13 09:27:58
What is a separable graph?
1.A disconnected graph by deleting a vertex
2.A disconnected graph by removing an edge
3.A disconnected graph by removing one edge and a vertex
4.A simple graph which does not contain a cycle
Posted Date:-2022-05-13 09:31:30
What is a star tree?
1.A tree having a single internal vertex and n-1 leaves
2.A tree having n vertices arranged in a line
3.A tree which has 0 or more connected subtrees
4.A tree which contains n vertices and n-1 cycles
Posted Date:-2022-05-13 09:22:30
What is the grade of a planar graph consisting of 8 vertices and 15 edges?
1.30
2.15
3. 45
4.106
Posted Date:-2022-05-13 09:51:42
What is the number of vertices in an undirected connected graph with 39 edges, 7 vertices of degree 2, 2 vertices of degree 5 and remaining of degree 6?
1.11
2. 14
3.18
4.19
Posted Date:-2022-05-13 09:41:46
What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph?
1.Depends on a Graph
2.Will always be zero
3.Will always be greater than zero
4.May be zero or greater than zero
Posted Date:-2022-05-13 10:05:23
What is 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 S2 is greater than S1?
1.O(S1)
2.O(S2)
3.O(S1+S2)
4.O(1)
Posted Date:-2022-05-13 10:07:03
Which algorithm efficiently calculates the single source shortest paths in a Directed Acyclic Graph?
1.topological sort
2.hash table
3.binary search
4.radix sort
Posted Date:-2022-05-13 09:53:57
Which of the given statement is true?
1.All the Cyclic Directed Graphs have topological sortings
2.All the Acyclic Directed Graphs have topological sortings
3.All Directed Graphs have topological sortings
4.All the cyclic directed graphs hace non topological sortings
Posted Date:-2022-05-13 10:04:09