CREATE TEST

ERASED TEST, YOU MAY BE INTERESTED ON graphs 4

COMMENTS	STATISTICS	RECORDS

TAKE THE TEST

Title of test: graphs 4 Description: graph theory Author: Mark Ganus Other tests from this author Creation Date: 28/08/2024 Category: Computers Number of questions: 20

Share the Test:

New Comment

No comments about this test.

Content:

Consider the graph G below and the statements made about G: I. The graph is planar. -- So, no "X" shapes where two lines intersect. II. The shortest directed path measured in number of arcs between nodes D and F has length 2. III. DABCEF represents a valid topological ordering of the nodes of the graph. IV. There is some directed path between D and all other nodes of the graph. V. The largest strongly connected component of G is composed of a single node, that is, there does not exist in G a pair of distinct nodes x and y that have a directed path between x and y and a directed path between y and x. Which are correct? HINT: A planar graph is a type of graph that you can draw on a flat surface (like a piece of paper) without any of its edges (lines connecting points) crossing each other. Imagine you have a bunch of dots (points) connected by lines, and you can arrange them so that none of the lines overlap. If you can do that, the graph is called planar. A) Only II and III. B) Only I, II and IV. C) Only I, III and V. D) Only I, II, III and V. E) I, II, III, IV and V. Select the correct alternative regarding the basic definitions of graphs. A) A hypergraph is a directed graph in which each edge connects only two vertices. B) A weighted graph is an undirected graph in which all pairs of vertices are adjacent to each other. C) A forest is an acyclic and connected undirected graph. D) A free tree is an acyclic undirected graph, which may or may not be connected. E) A directed graph is strongly connected if any two vertices are reachable from each other. Edges are explored from the most recently discovered vertex v that still has unexplored edges leading from it. When all edges adjacent to v have been explored, the search moves backwards to explore vertices leading from the vertex from which v was discovered. The process continues until all vertices reachable from the original vertex have been discovered. Which graph algorithm has the strategy described above? A) Topological sort. B) Depth-first search. C) Strongly connected components. D) Minimum spanning tree. E) Breadth-first search. Regarding topological ordering in graphs, it is correct to state that: A) Breadth-first search is used to obtain the topological ordering of a directed acyclic graph. B) The topological ordering of a graph can be seen as an ordering of its edges along a horizontal line, such that all vertices are classified in ascending order. C) The topological ordering of a directed acyclic graph G=(V,A) is a linear ordering of all its vertices such that G contains an edge (u, v), so u appears before v. D) Binary search is used to obtain the topological ordering of an undirected cyclic graph. E) The algorithm to obtain the topological ordering of a directed graph uses the transpose of the graph, which consists of all edges with their directions reversed. Consider the grammar G described to the right: set of terminals {a,c}, set of non-terminals {S,A}, initial symbol S and containing the productions below: S -> AcS S -> A A -> aAa A -> a Also consider the finite automaton A over the alphabet {a,c}, with set of states {q0,q1,q2} — of which q0 is initial and q1 is final — and with state transition function determined by the following graph: If L(G) is the language generated by grammar G and L(A) is the language recognized by automaton A, select the correct alternative. L(G) is regular and L(A) is a proper subset of L(G). L(G) is not regular and L(A) is a proper subset of L(G). L(A) = L(G). L(G) is regular and L(G) is a proper subset of L(A). L(G) is not regular and L(G) is a proper subset of L(A). About graphs, select the correct alternative. A) A weighted graph is an undirected graph in which all pairs of vertices are adjacent, that is, there are edges connecting all vertices to each other. B) Every complete graph has weights associated with its edges. C) A path in a graph is complex if all vertices of the path are distinct. D) The degree of a vertex in an undirected graph is the number of edges that fall on it. E) If there exists a path c from x to y, then x is reachable from c via y. A road map is modeled as a graph in which vertices represent intersections. Edges represent road segments between intersections. The weight of each edge represents the distance between intersections. Now, consider that a driver wants to find the shortest path between two cities. Given a map containing the distances between each pair of adjacent intersections, how can he find the shortest path between two cities? A) Shortest path with a single destination. B) Minimum spanning path with a single origin. C) Shortest path with a single origin. D) Shortest path between all pairs of vertices. E) Minimum spanning path with multiple origins. Given a graph G and a source vertex, what is the search algorithm that discovers all vertices at a distance K from the source vertex, before discovering any vertex at a distance K+1? A) Preorder. B) Breadth-first. C) Postorder. D) Depth-first. E) Symmetric. Consider the following statements about problem classes: I. The CAM decision problem, described below, belongs to the complexity class P. CAM (path in graph) Input: a triple (G,a,b) where - G is a graph - a and b are nodes of G Question: Is there a path in G starting at a and ending at b? II. A problem X belongs to the class of NP-complete problems when it satisfies the following conditions: - X belongs to the class NP, and - every problem Y of the class NP can be reduced in polynomial time to X. Which are correct? A) Only I. B) Only III. C) Only I and II. D) Only II and III. E) I, II, and III. According to Type System Theory, classify the following function: int sum(int x,int y) { return x+y; } A monomorphic function is a function that operates on a single type or a specific data type, as opposed to a polymorphic function that can operate on multiple types. In summary: Adder function: Performs addition. Monomorphic function: Works with a single specific data type. A) Adder Function. B) Polymorphic Function. C) Monomorphic Function. D) Overloaded Function. E) Abstract Function. Given a graph G and a source vertex, what is the search algorithm that discovers all vertices at a distance K from the source vertex, before discovering any vertex at a distance K+1? hint 1: It explores the neighbour vertices layer by layer, starting from the source vertex. thus, all vertices at distance K are discovered before any further vertices hint 2: k + 1 A) Preorder. B) Breadth-first. C) Postorder. D) Depth-first. E) Symmetric. The MergeSort sorting algorithm, the Kruskal minimum spanning tree, and the Floyd-Warshall algorithm that calculates the shortest path between all pairs of vertices of a weighted directed graph are, respectively, examples of algorithms: A) Greedy, dynamic programming, and divide and conquer. B) Divide and conquer, dynamic programming, and greedy. C) Greedy, divide and conquer, and dynamic programming. D) Dynamic programming, divide and conquer, and greedy. E) Divide and conquer, greedy, and dynamic programming. An undirected graph in which all pairs of vertices are adjacent, that is, it has edges connecting all vertices to each other, is a graph that is: A) Disconnected. B) Complete. C) Weighted. D) Free. E) Hypergraph. is the implementation in which a graph G = (V,A) containing n vertices is an n x n bit matrix, in which 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. A) Incidence matrix. B) Adjacency list. C) Adjacency matrix. D) Incidence list. E) Complete square matrix. What is the graph search algorithm in which the search starts from a root node and traverses each path in order to go as far as possible before moving on to another path? A) Topological. B) Breadth-first. C) Coverage. D) Post-order. E) Depth-first. The complement of a graph G(V,E) is the graph H that has the set of vertices equal to that of G and such that, for every pair of distinct vertices v,w in V, we have that the edge (v,w) is an edge of G if and only if (v,w) is not an edge of H. In this regard, indicate the CORRECT statement. A) G and H are isomorphic graphs. B) If graph G is connected, then H is connected. C) If graph G is not connected, then H is connected. D) If graph G is not connected, then H is not connected. E) Graphs G and H have the same number of connected components. A graph G(V,E) is a tree if G is connected and acyclic. Indicate the definition that CANNOT be used to define trees. A) G is connected and the number of edges is minimal. B) G is connected and the number of vertices exceeds the number of edges by one. C) G is acyclic and the number of vertices exceeds the number of edges by one. D) G is acyclic and for every pair of vertices v, w that are not adjacent in G, the addition of the edge (v,w) produces a graph containing exactly one cycle. E) G is acyclic and the number of edges is minimal. In a graph G(V,E), the degree of a vertex is the number of vertices adjacent to v. In this regard, indicate the CORRECT statement. HINT: look up the handshaking dilemma A) In a graph, the number of vertices with odd degree is always even. B) In a graph, the number of vertices with even degree is always odd. C) In a graph, there is always some vertex with even degree. D) In ​​a graph, there is always some vertex with odd degree. E) In a graph, the number of vertices with odd degree is always equal to the number of vertices with even degree. Consider graphs I, II, III, IV and V, shown below: They are isomorphic graphs A) all of the above. B) only I and III. C) only II and V. D) only III and IV. E) only I, II and III. Let G (V, E) be a graph such that |V | n and | E | m . Analyze the following sentences: I. If G is acyclic with at most n 1 edges, then G is a tree. II. If G is a cycle, then G has n distinct spanning trees. III. If G is connected with at most n 1 edges, then G is a tree. IV. If G is connected and has a cycle, then for every spanning tree T of G , E(G) - E(T) != {empty} The analysis allows us to conclude that A) only items I and III are true. B) only Items II and III are true. C) only Item I is false. D) all items are true. E) only items II and IV are true.

Report abuse