Terminal Exam-June 21,2020

A highly detailed and artistic representation of a complex graph with vertices and edges, annotated with mathematical symbols and algorithmic notations, vibrant colors and a modern digital look.

Graph Theory Challenge Quiz

Test your knowledge of graph theory and algorithms with our comprehensive quiz designed for students and enthusiasts alike. This quiz features 51 questions covering various aspects of graph theory, including minimum cuts, vertices, edges, and more.

Are you ready to dive in? Here are some key points:

51 Multiple Choice Questions
Focus on algorithms and graph properties
Great for students and professionals

51 Questions13 MinutesCreated by AnalyzingGraph32

Please Enter your full registration number

Which one is the correct problematic edge discovered, if algorithm is applied on given graph to get a clean graph ,and the first path discovered is 1-4-3-6(1:source vertex, 6:destination vertex).

Edge from 2-5

Edges from 2-3

Edge from 4-3

Edge from 5-6

Considering the above graph, the size of minimum cut in original graph will be:

None

The path finder tool, that deletes the path after discovering did not work well because:

It destroyed other possible paths

It discovered incorrect paths

Its time complexity is high

It lost the vertices

If the number of edges in the cut in original graph is greater than the number of reversed edges in the transformed graph (i.e. Resultant graph of algo 5.2), it means

Minimum cut has been found

The number of edge disjoint paths equal to size of thi cut

There is still a path available for traversal

Problematic edges has been discovered

If the number of reversed edges in transformed graph are 4, the number of pseudo edge disjoint paths will be

If an edge is destroyed ,that is inside the minimum cut, the maximum number of edge disjoint paths will:

Increase

Decrease

Will not be affected

Consider a graph where, the source and destination vertex is connected directly, the size of min cut will be

Equal to no of edges involved

None

The number of vertex disjoint paths in Graph H are

If there are 4 edge disjoint paths in a graph with 8 vertices, the possible number of vertex disjoint paths in same graph will be:

If a given vertex x is split in two vertices x1 and x2, the out degree of x1 and x2 respectively will be:

1,1

1,2

Can be any,1

1,can be any

While finding the 2-edge shortest paths from any source vertex a to k in any graph, the new edge will be added if:

The weight of directed edge from a to k is less than weight of two edge path from a to k

The weight of directed edge from a to k is smaller than weight of two edge path from a to k

Using Dijkistra's algorithm, 2 edge shortest path cannot be found correctly because:

Paths are discovered through vertex recently added in the bucket

Paths are discovered through weights of 2-edge paths

Paths discovered are not shortest paths

This step is performed in which of the algorithm?

Algorithm to find the single source shortest path

Algorithm to find the shortest paths between all the vertices

Algorithm to find the 2-edge shortest paths.

Both b & c

The given pseudocode is for which algorithm?

Floyed Warshall

Slow all pair shortest path

BellmanFord

Single source shortest path

If there ia a negative weight cycle in a graph and a loop keeps running inside that cycle, the weight of shortest path will keep:

Increasing

Decreasing

Remain constant

Which will be the cheapest algorithm to find the all pairs shortest paths in any graph with all edges having positive weights?

Fastest all pair shortest path algo

Floyd Warshall algo

Dijkstra Algo

If there is a change in shortest path from lets assume p-3 to p-2 edge long paths of any graph then:

A negative cycle in graph is confirmed

There may be a negative cycle

There may not be a negative cycle

Both b & c

In a graph if the total number of vertices are 10 , the number of edges attached to the super vertex will be?

The graph S4 is:

Chain Graph

Regular Graph

Star Graph

Are these two graphs isomorphic?

Yes

All connected graphs are always complete graphs

True

False

The sum of degrees of all vertices will always be even if

The graph is directed

The graph is undirected

The graph is regular

The graph is cyclic

The sum of 1's in the adjacency matrix for undirected graph is 10, the number of edges in the said graph will be:

Adjacency matrix for undirected graph should always have 0's at diagonal.

True

False

_____________ of adjacency matrix shows the degree of the vertex.

Number of 1's in column of that vertex

Number of 1's in rows of that vertex

Number of 1's at diagonal of matrix

Is the given Graph self complementary graph?

Yes

The degree of every vertex in a regular self complementing Graph of total vertices 7 is:

Any regular graph with 9 vertices can be self complementing graph if, the degree of each vertex is:

The graph having degree sequence 543221 can be self complementing?

Yes

______ graph shows symmetry on both sides of the diagonal of its adjacency matrix

Graph with self loops

Undirected Graph

Directed Graph

If a simple path has total number of edges less than p, that means

Cycle exists

Cycle does not exist

It is a tree

The degree sequence of a complement is same as the degree sequence of original graph.

True

False

Considering the modified MST algorithm to find the shortest path, which vertex should go into the bucket next.

Time complexity to find the shortest paths through adjacency list is p*Q because:

All the edges are visited once

All the edges are visited in every step

Vertces are always multiplied with edges while calculating lists complexity

If the basic building block of algorithm from 1-edge path to 2-edge path is carried out p times, it becomes

Slow all pair shortest path algo

Bellman Ford Algorithm

Dijkstra algo

Considering the graph with all positive edge weights, in slow all pairs shortest path algorithm, if the inner most two ,loops are interchanged, the results will be inversed.

True

False

We can find bridge edges in a graph by using:

Bucket algorithm

Spanning Tree

Both a &b

None of these

While cutting edges of graphs to form a spanning tree, which of the following condition should be fulfilled?

The edge removed is not a bridge edge

The edge removed does not create a cycle

The graph is still connected

Both a &c

The selecting edges with minimum weights to find the MST, this algo is also called

Prims algo

Krushkal algo

Dijkstra algo

In the figure, the yellow edges are removed, which algorithm is shown by the given figure?

Prim's

Krushkal's

Dijkstra

BFS gives incorrect shortest paths in case of :

Directed graphs

Undirected graphs

Cyclic

Minimum spanning tree can find the correct shortest path in weighted graphs

True

False

There can be a spanning tree for the given graph, that has lower weight than bottle neck spanning tree

True

False

Using matrices, the basic idea of using an algorithm to find the complement of a graph is:

Assign 1 to all, the cells

Convert 1's to zeros and 0's to 1's

Remove 1's from matrix

Assign 0 to all cells

Which is the complement matrix for the given matrix?

A cycle graph has

Atleast 1 cycle

More than 1 no of cycles

Exactly 1 cycle

If at any cell xy in a matrix, there is a zero that should remain zero, and if there is 1,it should be removed from xy and put in yx,the procedure is performed for

Complement of a graph

Addition of a graph amd its complement

Transponse of a graph

Addition of graph and its transponse

A simple crude form of bucket algorithm helps checking

Graph is regular

Graph is connected

Number of vertices attached toa particular vertex

The time complexity to find the transpose of a graph using adjacency list is:

P^2

P*q

P+q

The degree of each vertex in a completely connected graph with 6 number of vertices is

Unlock and Upgrade

Remove all limits from your Quizzes

Terminal Exam-June 21,2020

Graph Theory Challenge Quiz

More Quizzes