COMPUTER SCIENCE AND ENGINEERING
DATA STRUCTURES
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
15
|
|
|
1
|
|
|
3
|
|
|
11
|
Detailed explanation-1: -A connected planar graph having 6 vertices, 7 edges contains regions. a) 15b) 3c) 1d) 11Answer: bExplanation: By euler’s formula the relation between vertices(n), edges(q) and regions(r) is given byn-q+r=2. 8.
Detailed explanation-2: -Solution Having six vertices each of degree 4, thanks to the handshaking theorem we get that the number of edges is: 12 By using Euler $ formula we get T = e-V+2 T =42-6+2 = 8.
Detailed explanation-3: -For all planar graphs, 3|F| 2|E|, where |F| is the number of faces and |E| is the number of edges. of a planar graph ensures that we have at least a certain number of edges. Figure 21: The complete graph on five vertices, K5. 7 = 10.5 edges.
Detailed explanation-4: -Theorem: [Euler’s Formula] For a connected planar simple graph G=(V, E) with e=|E| and v=|V|, if we let r be the number of regions that are created when drawing a planar representation of the graph, then r=e-v+2. Proof idea: We proceed by induction on the number of edges.