Graph Theory GeeksforGeeks

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