Baixe o app para aproveitar ainda mais
Prévia do material em texto
Practice GATE CS Placements Videos Contribute Login/Register Popular Tags Amazon, Microsoft, Dynamic Programming, Samsung Click here for more Interview Preparation Step by Step Preparation Company Preparation Top Topics Company Specific Practice Software Design Patterns Placements Preparation Course Interview Corner Recent Interview Experiences GQ Home Page Quiz Corner LMNs Practice Platform Graph Theory - GeeksforGeeks http://www.geeksforgeeks.org/graph-theory-gq/ 1 of 10 8/26/17, 9:43 PM What's New ? Leaderboard !! Topic-wise Practice Subjective Problems Difficulty Level - School Difficulty Level - Basic Difficulty Level - Easy Difficulty Level - Medium Difficulty Level - Hard How to pick a difficulty level? Explore More... Programming Languages C C++ Java Python SQL Important Quick Links School Programming Operating Systems DBMS Computer Networks Engineering Mathematics Design Patterns ▲ Graph Theory - GeeksforGeeks http://www.geeksforgeeks.org/graph-theory-gq/ 2 of 10 8/26/17, 9:43 PM Question 11 CORRECT No two vertices have the same degree. At least two vertices have the same degree. At least three vertices have the same degree. All vertices have the same degree. Question 12 CORRECT 1 2 3 4 5 Graph Theory Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices? GATE-CS-2009 Graph Theory Discuss it Question 11 Explanation: Since the graph is simple, there must not be any self loop and parallel edges. Since the graph is connected, the degree of any vertex cannot be 0. Therefore, degree of all ver- tices should be be from 1 to n-1. So the degree of at least two vertices must be same. Which of the following statements is true for every planar graph on n vertices? Common Interview Puzzles Web Technology G-Facts Computer Graphics Image Processing Project Ideas ▲ Graph Theory - GeeksforGeeks http://www.geeksforgeeks.org/graph-theory-gq/ 3 of 10 8/26/17, 9:43 PM The graph is connected The graph is Eulerian The graph has a vertex-cover of size at most 3n/4 The graph has an independent set of size at least n/3 Question 13 WRONG For every subset of k vertices, the induced subgraph has at most 2k-2 edges The minimum cut in G has at least two edges There are two edge-disjoint paths between every pair to vertices There are two vertex-disjoint paths between every pair of vertices Graph Theory GATE CS 2008 Discuss it Question 12 Explanation: A planar graph is a graph which can drawn on a plan without any pair of edges crossing each other. A) FALSE: A disconnected graph can be planar as it can be drawn on a plane without crossing edges. B) FALSE: An Eulerian Graph may or may not be planar. An undirected graph is eulerian if all vertices have even degree. For example, the follow- ing graph is Eulerian, but not planar C) TRUE: D) FALSE: G is a graph on n vertices and 2n - 2 edges. The edges of G can be partitioned into two edge-dis- joint spanning trees. Which of the following is NOT true for G? Graph Theory GATE CS 2008 Discuss it ▲ Graph Theory - GeeksforGeeks http://www.geeksforgeeks.org/graph-theory-gq/ 4 of 10 8/26/17, 9:43 PM Question 14 WRONG 9 edges and 5 vertices 9 edges and 6 vertices 10 edges and 5 vertices 10 edges and 6 vertices Question 15 CORRECT Any k-regular graph where kis an even number. Question 13 Explanation: Counter for option D is as follows. Take two copies of K4(complete graph on 4 vertices), G1 and G2. Let V(G1)={1,2,3,4} and V(G2)={5,6,7,8}. Construct a new graph G3 by us- ing these two graphs G1 and G2 by merging at a vertex, say merge (4,5). The resultant graph is two edge connected, and of minimum degree 2 but there exist a cut vertex, the merged vertex. Thanks to Renjith P for providing above explanation. Let G be the non-planar graph with the minimum possible number of edges. Then G has Graph Theory GATE-CS-2007 Discuss it Question 14 Explanation: For a simple, connected, planar graph with v vertices and e edges, the following simple conditions hold: If v ≥ 3 then e ≤ 3v − 6; Note that the question is about non-planar graph G. Only option C doesn't follow above. Alternate Explanation: We know that K5K5 (which has 10 edges and 5 vertices) and K3,3K3,3 (which has 9 edges and 6 vertices) are non-planar graphs. Since we are asked about minimum number of edges, answer should be k3,3k3,3 i.e. option (B) is correct. Source: http://www.cse.iitd.ac.in/~mittal/gate/gate_math_2007.html Which of the following graphs has an Eulerian circuit? ▲ Graph Theory - GeeksforGeeks http://www.geeksforgeeks.org/graph-theory-gq/ 5 of 10 8/26/17, 9:43 PM A complete graph on 90 vertices The complement of a cycle on 25 vertices None of the above Question 16 WRONG A B C D Graph Theory GATE-CS-2007 Discuss it Question 15 Explanation: A graph has Eulerian Circuit if following conditions are true. ….a) All vertices with non- zero degree are connected. We don’t care about vertices with zero degree because they don’t belong to Eulerian Cycle or Path (we only consider all edges). ….b) All vertices have even degree. Let us analyze all options. A) Any k-regular graph where k is an even number. is not Eulerian as a k regular graph may not be connected (property b is true, but a may not) B) A complete graph on 90 vertices is not Eulerian because all vertices have degree as 89 (property b is false) C) The complement of a cycle on 25 vertices is Eulerian. In a cycle of 25 vertices, all vertices have degree as 2. In comple- ment graph, all vertices would have degree as 22 and graph would be connected. Let G=(V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G ? Graph Theory GATE-CS-2014-(Set-1) Discuss it ▲ Graph Theory - GeeksforGeeks http://www.geeksforgeeks.org/graph-theory-gq/ 6 of 10 8/26/17, 9:43 PM Question 17 CORRECT 500 502 506 510 Question 16 Explanation: If we reverse directions of all arcs in a graph, the new graph has same set of strongly connected components as the original graph. Se http://www.geeksforgeeks.org/strongly- connected-components/ for more details. Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i, j): 1 <= i <= 12, 1 <= j <= 12}. There is an edge between (a, b) and (c, d) if |a − c| <= 1 and |b − d| <= 1. The number of edges in this graph is __________. Graph Theory GATE-CS-2014-(Set-1) Discuss it Question 17 Explanation: Given: The vertex set of G is {(i, j): 1 <= i <= 12, 1 <= j <= 12}. There is an edge between (a, b) and (c, d) if |a − c| <= 1 and |b − d| <= 1. There can be total 12*12 possible vertices. The vertices are (1, 1), (1, 2) ....(1, 12) (2, 1), (2, 2), .... The number of edges in this graph? Number of edges is equal to number of pairs of vertices that satisfy above conditions. For example, vertex pair {(1, 1), (1, 2)} satisfy above condition. For (1, 1), there can be an edge to (1, 2), (2, 1), (2, 2). Note that there can be self‐loop as mentioned in the question. Same is count for (12, 12), (1, 12) and (12, 1) For (1, 2), there can be an edge to (1, 1), (2, 1), (2, 2), (2, 3), (1, 3) Same is count for (1, 3), (1, 4)....(1, 11), (12, 2), ....(12, 11) ▲ Graph Theory - GeeksforGeeks http://www.geeksforgeeks.org/graph-theory-gq/ 7 of 10 8/26/17, 9:43 PM Question 18 (1, 1, 1, 1, 1, 1) (2, 2, 2, 2, 2, 2) (3, 3, 3, 1, 0, 0) (3, 2, 1, 1, 1, 0) Question 19 For (2, 2), therecan be an edge to (1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), (3, 3) Same is count for remaining vertices. For all pairs (i, j) there can total 8 vertices connected to them if i and j are not in {1, 12} There are total 100 vertices without a 1 or 12. So total 800 edges. For vertices with 1, total edges = (Edges where 1 is first part) + (Edges where 1 is second part and not first part) = (3 + 5*10 + 3) + (5*10) edges Same is count for vertices with 12 Total number of edges: = 800 + [(3 + 5*10 + 3) + 5*10] + [(3 + 5*10 + 3) + 5*10] = 800 + 106 + 106 = 1012 Since graph is undirected, two edges from v1 to v2 and v2 to v1 should be counted as one. So total number of undirected edges = 1012/2 = 506. An ordered n-tuple (d1, d2, … , dn) with d1 >= d2 >= ⋯ >= dn is called graphic if there exists a simple undirected graph with n vertices having degrees d1, d2, … , dn respectively. Which of the following 6-tuples is NOT graphic? Graph Theory GATE-CS-2014-(Set-1) Discuss it The maximum number of edges in a bipartite graph on 12 vertices is ▲ Graph Theory - GeeksforGeeks http://www.geeksforgeeks.org/graph-theory-gq/ 8 of 10 8/26/17, 9:43 PM 36 Question 20 2 4 6 5 __________________________. Graph Theory GATE-CS-2014-(Set-2) Discuss it A cycle on n vertices is isomorphic to its complement. The value of n is _____. Graph Theory GATE-CS-2014-(Set-2) Discuss it You have completed 14/43 questions . Your accuracy is 57%. 1 2 3 4 5 ▲ Graph Theory - GeeksforGeeks http://www.geeksforgeeks.org/graph-theory-gq/ 9 of 10 8/26/17, 9:43 PM Writing code in comment? Please use ide.geeksforgeeks.org, generate link and share the link here. 0 Comments Login � 1 Share � Sort by Newest LOG IN WITH OR SIGN UP WITH DISQUS Start the discussion… ? Recommend � 1 @geeksforgeeks, Some rights reserved Contact Us! About Us! Careers! Privacy Policy ▲ Graph Theory - GeeksforGeeks http://www.geeksforgeeks.org/graph-theory-gq/ 10 of 10 8/26/17, 9:43 PM
Compartilhar