Consider an undirected random graph of eight vertices. The probability — PYQDeck

PyQdeckBEU PYQ Archive Subjects

Back to the 2019 paper

Module 4: Graph and Tree Algorithms

20192m

Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is $1/2$ . What is the expected number of unordered cycles of length three?

(i) 1/8
(ii) 1
(iii) 8
(iv) 8

Search Google Ask AI

Similar questions

Discrete MathematicsThe number of edges in a regular graph of degree 46 and 8 vertices is (i) 347 (ii) 230 (iii) 184 (iv) 18620222m Discrete MathematicsAn undirected graph has 8 vertices labelled 1, 2, \dots, 8 and 31 edges. Vertices 1, 3, 5, 7 have degree 8 and vertices 2, 4, 6, 8 have degree 7. What is the degree of vertex 8? (i) 15 (ii) 8 (iii) 5 (iv) 2320222m Design and Analysis of Algorithms A graph with five nodes is represented using the adjacency list as follows: | | | | | | |---|---|---|---|---| | A | -> | B (10) | C (3) | | | B | -> | C (1) | D (5) | | | C | -> | B (4) | D (8) | E (2) | | D | -> | E (7) | | | | E | -> | D (9) | | | Answer the following: (i) Draw the graph for the above adjacency list. (ii) Write the algorithm for the Breadth-First Traversal (BFS). (iii) Show the BFS traversal of the graph with the starting node as A.20247m Design and Analysis of Algorithms The minimum number of colors needed to color a graph having n > 3 vertices and 2 edges is (i) 2 (ii) 3 (iii) 4 (iv) 120222m

PreviousTime complexity of Kadane's Algorithm is: - (i) O(n) - (ii) O(n^2) - (iii) O(n \log n) - (iv) O(n(\log n)^2)NextAny decision tree that sorts n elements has height: - (i) \Omega(\lg n) - (ii) \Omega(n) - (iii) \Omega(n \lg n) - (iv) \Omega(n^2)