Back
0

Algebraic Graph Theory

Description: Algebraic Graph Theory Quiz
Number of Questions: 15
Created by:
Tags: algebraic graph theory graph theory mathematics
Start the Quiz
Attempted 0/15 Correct 0 Score 0
‹
›

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.

Show answer
Correct Option: A
Explanation:

The adjacency matrix of a graph is a square matrix whose rows and columns are labeled by the vertices of the graph. The entry in the $i$th row and $j$th column of the adjacency matrix is the weight of the edge between vertices $i$ and $j$, if there is an edge between them, and $0$ otherwise.

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.

Show answer
Correct Option: A
Explanation:

The degree of a vertex in a graph is the number of edges that are incident to the vertex. In other words, it is the number of vertices that are adjacent to the vertex.

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.

Show answer
Correct Option: A
Explanation:

The Laplacian matrix of a graph is a square matrix whose rows and columns are labeled by the vertices of the graph. The entry in the $i$th row and $j$th column of the Laplacian matrix is the degree of vertex $i$ if $i = j$, and $-1$ if $i eq j$ and there is an edge between vertices $i$ and $j$, and $0$ otherwise.

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.

Show answer
Correct Option: A
Explanation:

The spectrum of a graph is the set of all eigenvalues of the adjacency matrix of the graph.

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.

Show answer
Correct Option: A
Explanation:

The chromatic number of a graph is the minimum number of colors needed to color the vertices of the graph so that no two adjacent vertices have the same color.

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.

Show answer
Correct Option: A
Explanation:

The clique number of a graph is the maximum number of vertices in a clique in the graph.

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.

Show answer
Correct Option: A
Explanation:

The independence number of a graph is the maximum number of vertices in an independent set in the graph.

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.

Show answer
Correct Option: A
Explanation:

The domination number of a graph is the minimum number of vertices in a dominating set in the graph.

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.

Show answer
Correct Option: A
Explanation:

The matching number of a graph is the maximum number of edges in a matching in the graph.

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.

Show answer
Correct Option: A
Explanation:

The vertex cover number of a graph is the minimum number of vertices in a vertex cover in the graph.

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.

Show answer
Correct Option: A
Explanation:

The edge cover number of a graph is the minimum number of edges in an edge cover in the graph.

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.

Show answer
Correct Option: A
Explanation:

The Hamiltonian cycle problem is the problem of finding a cycle in a graph that visits every vertex exactly once.

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.

Show answer
Correct Option: A
Explanation:

The traveling salesman problem is the problem of finding a tour in a graph that visits every vertex exactly once and minimizes the total weight of the tour.

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.

Show answer
Correct Option: A
Explanation:

The maximum clique problem is the problem of finding a clique of maximum size in a graph.

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.

Show answer
Correct Option: A
Explanation:

The maximum independent set problem is the problem of finding an independent set of maximum size in a graph.

- Hide questions
ADVERTISEMENT

Find more quizzes from top tags

general knowledge
3615 Quizzes
119858 Questions
 technology
307 Quizzes
36705 Questions
 sports
963 Quizzes
19148 Questions
 history
1187 Quizzes
13475 Questions
 physics
598 Quizzes
13441 Questions
 biology
1160 Quizzes
12174 Questions
 science & technology
551 Quizzes
11015 Questions
 chemistry
490 Quizzes
9892 Questions
 maths
518 Quizzes
9324 Questions
 softskills
0 Quizzes
7131 Questions