Home › Quizzes › Algebraic Graph Theory

Algebraic Graph Theory

Algebraic Graph Theory Quiz

15 Questions Published
Play Quiz Practise this topic out loud

Questions

Question 1 Multiple Choice (Single Answer)

What is the adjacency matrix of a graph?

  1. A matrix whose entries are the weights of the edges of the graph.
  2. A matrix whose entries are the degrees of the vertices of the graph.
  3. A matrix whose entries are the distances between the vertices of the graph.
  4. A matrix whose entries are the eigenvalues of the graph.
Question 2 Multiple Choice (Single Answer)

What is the degree of a vertex in a graph?

  1. The number of edges incident to the vertex.
  2. The number of vertices adjacent to the vertex.
  3. The sum of the weights of the edges incident to the vertex.
  4. The maximum distance between the vertex and any other vertex in the graph.
Question 3 Multiple Choice (Single Answer)

What is the Laplacian matrix of a graph?

  1. A matrix whose entries are the degrees of the vertices of the graph.
  2. A matrix whose entries are the distances between the vertices of the graph.
  3. A matrix whose entries are the eigenvalues of the graph.
  4. A matrix whose entries are the weights of the edges of the graph.
Question 4 Multiple Choice (Single Answer)

What is the spectrum of a graph?

  1. The set of all eigenvalues of the adjacency matrix of the graph.
  2. The set of all eigenvalues of the Laplacian matrix of the graph.
  3. The set of all eigenvalues of the incidence matrix of the graph.
  4. The set of all eigenvalues of the distance matrix of the graph.
Question 5 Multiple Choice (Single Answer)

What is the chromatic number of a graph?

  1. The minimum number of colors needed to color the vertices of the graph so that no two adjacent vertices have the same color.
  2. The maximum number of colors needed to color the vertices of the graph so that no two adjacent vertices have the same color.
  3. The number of vertices in the graph.
  4. The number of edges in the graph.
Question 6 Multiple Choice (Single Answer)

What is the clique number of a graph?

  1. The maximum number of vertices in a clique in the graph.
  2. The minimum number of vertices in a clique in the graph.
  3. The number of cliques in the graph.
  4. The size of the largest independent set in the graph.
Question 7 Multiple Choice (Single Answer)

What is the independence number of a graph?

  1. The maximum number of vertices in an independent set in the graph.
  2. The minimum number of vertices in an independent set in the graph.
  3. The number of independent sets in the graph.
  4. The size of the largest clique in the graph.
Question 8 Multiple Choice (Single Answer)

What is the domination number of a graph?

  1. The minimum number of vertices in a dominating set in the graph.
  2. The maximum number of vertices in a dominating set in the graph.
  3. The number of dominating sets in the graph.
  4. The size of the largest independent set in the graph.
Question 9 Multiple Choice (Single Answer)

What is the matching number of a graph?

  1. The maximum number of edges in a matching in the graph.
  2. The minimum number of edges in a matching in the graph.
  3. The number of matchings in the graph.
  4. The size of the largest independent set in the graph.
Question 10 Multiple Choice (Single Answer)

What is the vertex cover number of a graph?

  1. The minimum number of vertices in a vertex cover in the graph.
  2. The maximum number of vertices in a vertex cover in the graph.
  3. The number of vertex covers in the graph.
  4. The size of the largest independent set in the graph.
Question 11 Multiple Choice (Single Answer)

What is the edge cover number of a graph?

  1. The minimum number of edges in an edge cover in the graph.
  2. The maximum number of edges in an edge cover in the graph.
  3. The number of edge covers in the graph.
  4. The size of the largest independent set in the graph.
Question 12 Multiple Choice (Single Answer)

What is the Hamiltonian cycle problem?

  1. Given a graph, find a cycle that visits every vertex exactly once.
  2. Given a graph, find a cycle that visits every edge exactly once.
  3. Given a graph, find a path that visits every vertex exactly once.
  4. Given a graph, find a path that visits every edge exactly once.
Question 13 Multiple Choice (Single Answer)

What is the traveling salesman problem?

  1. Given a graph and a set of weights on the edges, find a tour that visits every vertex exactly once and minimizes the total weight of the tour.
  2. Given a graph and a set of weights on the edges, find a tour that visits every edge exactly once and minimizes the total weight of the tour.
  3. Given a graph and a set of weights on the vertices, find a tour that visits every vertex exactly once and minimizes the total weight of the tour.
  4. Given a graph and a set of weights on the vertices, find a tour that visits every edge exactly once and minimizes the total weight of the tour.
Question 14 Multiple Choice (Single Answer)

What is the maximum clique problem?

  1. Given a graph, find a clique of maximum size.
  2. Given a graph, find a clique of minimum size.
  3. Given a graph, find a clique of maximum weight.
  4. Given a graph, find a clique of minimum weight.
Question 15 Multiple Choice (Single Answer)

What is the maximum independent set problem?

  1. Given a graph, find an independent set of maximum size.
  2. Given a graph, find an independent set of minimum size.
  3. Given a graph, find an independent set of maximum weight.
  4. Given a graph, find an independent set of minimum weight.
← Back to Quizzes