ERASED TEST, YOU MAY BE INTERESTED ON graphs 3
COMMENTS |
STATISTICS |
RECORDS
|
|---|
TAKE THE TEST
|
Title of test:
graphs 3 Description: graph theory Author: eyedol Other tests from this author Creation Date: 28/08/2024 Category: Computers Number of questions: 8 |
Share the Test:
New Comment
No comments about this test.
Content:
|
The matrix of a graph G = (V,A) containing n vertices is an n x n matrix of bits, where A[i,j] is 1 (or true, in the case of booleans) if and only if there exists an arc from vertex i to vertex j. This definition is a: A) Adjacency matrix for unweighted graphs. B) Recurrence matrix for unweighted graphs. C) Incidence matrix for unweighted graphs. D) Adjacency matrix for weighted graphs. E) Incidence matrix for weighted graphs. Figure (a) to the right shows an example of an undirected graph G with the weights shown next to each edge. Regarding the tree T represented in Figure (b), it is correct to state that: A) T represents the minimum spanning tree of the graph in Figure (a) whose total weight is 12. T is not unique, since replacing the edge (3,5) by the edge (2,5) produces another spanning tree with cost 12. B) T represents the tree of shortest paths between all pairs of vertices in the graph in Figure (a). T is not unique, since replacing the edge (3,5) by the edge (2,5) produces shorter paths between the same pairs of vertices in the graph. C) T represents the minimum spanning tree of the graph in Figure (a) whose total weight is 12. Replacing the edge (3,5) by the edge (2,4) produces a maximum spanning tree whose total weight is 14. D) T represents the topological ordering of the graph in Figure (a). The weight of the edge (0,2) indicates that it should be executed before the edge (2,3) and the weight of the edge (2,3) indicates that it should be executed before the edge (4,5) and so on. E) T represents the shortest path tree of the graph in Figure (a) with a single origin at vertex 2. T is not unique, since replacing the edge (3,5) with the edge (2,4) produces shortest paths between all pairs of vertices in the graph. Regarding Graph Theory, relate Column 1 to Column 2. Column 1 1. Complete Graph. 2. Hypergraph. 3. Free Tree. 4. Planar Graph. 5. Antiregular Undirected Graph. Column 2 ( ) Undirected graph, in which all pairs of vertices are adjacent to each other. ( ) Undirected graph in which each edge connects an arbitrary number of vertices, instead of connecting only two vertices. ( ) Acyclic and directed undirected graph. ( ) Graph in which its scheme can be drawn in a plane, so that any two edges touch, at most, at some end. ( ) Graph that has the greatest possible number of different degrees in its sequence. The correct order for filling in the parentheses, from top to bottom, is: A) 1 – 2 – 3 – 4 – 5. B) 2 – 3 – 4 – 5 – 1. C) 3 – 4 – 5 – 1 – 2. D) 4 – 5 – 1 – 2 – 3. E) 5 – 1 – 2 – 3 – 4. The graph labeled G(r), shown below, represents which regular expression? a b c d e. Regarding the syntax-directed translation technique, it is correct to state that: A) A syntax-directed definition is a context-free grammar with attributes and rules. The attributes are associated with the productions, and the rules with the terminal and non-terminal symbols of the grammar. B) A syntax-directed definition is called an S-attributed definition when only inherited attributes are involved. C) The semantic rules are only applied after the complete construction of the syntax tree by the compiler's parser. D) Dependency graphs are used to determine an evaluation order for the instances of the attributes of a derivation tree. E) Since “S” is a symbol of the grammar present in a derivation tree, a synthesized attribute is computed through the values of the attributes of the sibling nodes or the parent node of “S”. In relation to the graph in Figure (a), Figures (b) and (c) represent, respectively A) edge matrix and list of incidences. B) adjacency matrix and list of adjacency. C) connection matrix and list of edges. D) incidence matrix and list of vertices. E) vertex matrix and list of connections. Regarding graph paths, it is correct to state that a path: A) Is a family of successive incident connections, each one having an endpoint incident to the previous one and to the subsequent one. B) Is closed, if the last connection of the succession is adjacent to the first one. C) Open, cannot contain closed subpaths. D) Is elementary, if it does not repeat connections. E) Is simple, if it does not repeat vertices. The graph in Figure (a) to the right indicates precedence between activities. A directed edge (u,v) indicates that activity u must be performed before activity v. For example, activity 3 (represented by vertex 3) can only be started after activities 0 and 2 are finished, while activity 9 can be performed in any order. Figure (b) to the right shows for the graph in Figure (a) A) the strongly connected components that represent the activities that are mutually reachable from each vertex. B) the path between all activities, using the breadth-first search algorithm. C) the minimum spanning tree that represents all the possibilities of connection between activities, using the shortest possible flow between them. D) the path between all activities, using the depth-first search algorithm. E) the topological ordering that shows the order in which the activities should be processed. |
Report abuse