Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD .) (II) For every edge (u, v) of if u is at depth i and v is at depth j in TB , then | − | = 1. Which of the statements above must necessarily be true?

I only
II only
Both I and II
Neither I nor II

LohaHridoy

5 views

2025-01-04 04:42

1 Answers

AhmedNazir

Option 1 : I only

Undirected graph cant have cross edges in DFS forest. Hence statement 1 is TRUE.

Using triangle graph we can counter the second statement.

5 views Answered 2022-09-04 04:29

Related Questions

Consider the following statements: 1. Every natural number is a real number 2. Every real number is a rational number 3. Every integer is a real number 4. Every rational number is a real number Which of the above statements are correct?

1 Answers 5 Views

Consider the following statements in respect of two different non-zero integers p and q: I. For (p + q) to be less than (p - q), q must be negative II. For (p + q) to be greater than (p - q), both p and q must be positive Which of the above statements is/are correct?

1 Answers 4 Views

Consider a circle with centre at O and radius 7 cm. Let QR be the chord of length 2 cm and let P be the midpoint of QR. Let CD be another chord of this circle passing through P such that ∠CPQ is acute. If M is the midpoint of CD and MP = √24 cm, then which of the following statements are correct (1) ∠QPD = 135° (2) If CP = m cm and PD = n cm, then m and n are the roots of the quadratic equation x2 – 10x + 1 = 0 (3) The ratio of triangle OPR to the area of triangle OMP is 1 ∶ 2√2 Select the correct answer using the code given below.?

1 Answers 7 Views

The question given below has two statements I and II. These statements may be either independent causes or maybe effects of independent causes or a common cause. One of these statements may be the effect of the other statement. Read both the statements and decide which of these answer choices correctly depicts the relationship between the two statements. Statements: I. Majority of the residents of the housing society participated in the dinner hosted by one of the members of the society. II. Most of the people living in the housing society invite other members for the functions at their house.?

1 Answers 5 Views

Two processes X and Y need to access a critical section. Consider the following synchronization construct used by both the processes Process /* other code for process */ while(true) { varP = true; while(varQ == true) { /* Critical Section */ varP = false; } } /* other code for process */ Process /* other code for process */ while(true) { varQ = true; while(varP == true) { /* Critical Section */ varQ = false; } } /* other code for process */ Here, varP and varQ are shared variables and both are initialized to false. Which one of the following statements is true?

1 Answers 5 Views

Let G be an undirected connected graph with distinct edge weights . Let emax be the edge with maximum weight and emin be the edge with minimum weight. Which of the following statements is false.?

1 Answers 4 Views

A coin is tossed thrice. Let X be the event that head occurs in each of the first two tosses. Let Y be the event that a tail occurs on the third toss. Let Z be the event that two tails occur in three tosses. Based on the above information, which one of the following statements is TRUE?

1 Answers 5 Views

Let G be an undirected connected graph with distinct edge weight. Let emax be the edge maximum weight and emin the edge with minimum weight. Which of the following statements are false?

1 Answers 4 Views

Six boxes, M, N, O, P, Q and R, are kept one above the other but not necessarily in the same order. There is only one box between box N and box R. Box Q is immediately below box N. There are only two boxes between box Q and box M. There is no box above box P. Box R is third from the bottom. Which box is third from the top?

1 Answers 8 Views

Eight students A, B, C, D, E, F, G and H sit around a circular table, equidistant from each other, facing the centre of the table, not necessarily in the same order. B and D sit neither adjacent to C nor opposite to C. A sits in between E and D, and F sits in between B and H. Which one of the following is definitely correct?

1 Answers 5 Views

এক্সাম দিয়ে মেধা যাচাই করুন

Job Preparation (1125)

Admission (754)

এসএসসি (10)

এইচএসসি (5)