Algebraic Graph Theory
| Description: Algebraic Graph Theory Quiz | |
| Number of Questions: 15 | |
| Created by: Aliensbrain Bot | |
| Tags: algebraic graph theory graph theory mathematics |
What is the adjacency matrix of a graph?
-
A matrix whose entries are the weights of the edges of the graph.
-
A matrix whose entries are the degrees of the vertices of the graph.
-
A matrix whose entries are the distances between the vertices of the graph.
-
A matrix whose entries are the eigenvalues of the graph.
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?
-
The number of edges incident to the vertex.
-
The number of vertices adjacent to the vertex.
-
The sum of the weights of the edges incident to the vertex.
-
The maximum distance between the vertex and any other vertex in the graph.
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?
-
A matrix whose entries are the degrees of the vertices of the graph.
-
A matrix whose entries are the distances between the vertices of the graph.
-
A matrix whose entries are the eigenvalues of the graph.
-
A matrix whose entries are the weights of the edges of the graph.
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?
-
The set of all eigenvalues of the adjacency matrix of the graph.
-
The set of all eigenvalues of the Laplacian matrix of the graph.
-
The set of all eigenvalues of the incidence matrix of the graph.
-
The set of all eigenvalues of the distance matrix of the graph.
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?
-
The minimum number of colors needed to color the vertices of the graph so that no two adjacent vertices have the same color.
-
The maximum number of colors needed to color the vertices of the graph so that no two adjacent vertices have the same color.
-
The number of vertices in the graph.
-
The number of edges in the graph.
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?
-
The maximum number of vertices in a clique in the graph.
-
The minimum number of vertices in a clique in the graph.
-
The number of cliques in the graph.
-
The size of the largest independent set in the graph.
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?
-
The maximum number of vertices in an independent set in the graph.
-
The minimum number of vertices in an independent set in the graph.
-
The number of independent sets in the graph.
-
The size of the largest clique in the graph.
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?
-
The minimum number of vertices in a dominating set in the graph.
-
The maximum number of vertices in a dominating set in the graph.
-
The number of dominating sets in the graph.
-
The size of the largest independent set in the graph.
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?
-
The maximum number of edges in a matching in the graph.
-
The minimum number of edges in a matching in the graph.
-
The number of matchings in the graph.
-
The size of the largest independent set in the graph.
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?
-
The minimum number of vertices in a vertex cover in the graph.
-
The maximum number of vertices in a vertex cover in the graph.
-
The number of vertex covers in the graph.
-
The size of the largest independent set in the graph.
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?
-
The minimum number of edges in an edge cover in the graph.
-
The maximum number of edges in an edge cover in the graph.
-
The number of edge covers in the graph.
-
The size of the largest independent set in the graph.
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?
-
Given a graph, find a cycle that visits every vertex exactly once.
-
Given a graph, find a cycle that visits every edge exactly once.
-
Given a graph, find a path that visits every vertex exactly once.
-
Given a graph, find a path that visits every edge exactly once.
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?
-
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.
-
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.
-
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.
-
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.
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?
-
Given a graph, find a clique of maximum size.
-
Given a graph, find a clique of minimum size.
-
Given a graph, find a clique of maximum weight.
-
Given a graph, find a clique of minimum weight.
The maximum clique problem is the problem of finding a clique of maximum size in a graph.
What is the maximum independent set problem?
-
Given a graph, find an independent set of maximum size.
-
Given a graph, find an independent set of minimum size.
-
Given a graph, find an independent set of maximum weight.
-
Given a graph, find an independent set of minimum weight.
The maximum independent set problem is the problem of finding an independent set of maximum size in a graph.