GRAPHS QUIZ-1

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

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

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

• n*(n-1)

• n*(n+1)

The degree of any vertex of graph is ....

• The number of edges incident with vertex

• Number of vertex in a graph

• Number of vertices adjacent to that vertex

• Number of edges in a graph

The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph?

 I. 7, 6, 5, 4, 4, 3, 2, 1   II. 6, 6, 6, 6, 3, 3, 2, 2   III. 7, 6, 6, 4, 4, 3, 2, 2   IV. 8, 7, 7, 6, 4, 2, 1, 1

• I and II

• III and IV

• IV only

• II and IV

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

• Must be connected

• Must be unweighted

• Must have no loops or multiple edges

• All

Which of the following is true?

• A graph may contain no edges and many vertices

• A graph may contain many edges and no vertices

• A graph may contain no edges and no vertices

• None

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

• Multi Graph

• Regular Graph

• Simple Graph

• Complete Graph

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

• Adjacency List and Adjacency Matrix

• Incidence Matrix

• Adjacency List, Adjacency Matrix as well as Incidence Matrix

• No way to represent

What are the dimensions of an incidence matrix?

• Number of edges*number of edges

• Number of edges*number of vertices

• Number of vertices*number of vertices

• Number of edges (¹⁄₂ number of vertices)

DFS graph traversal uses _______ data structure

• Queue

• Stack

• Tree

• None

If a graph has 6 vertices then number of values in Adjacence matrix is _____