In directed graph G(V, E) where V = {P, Q, R, S, T} and E = {PQ, RS, TP, PS,…
2022
In directed graph G(V, E) where V = {P, Q, R, S, T} and E = {PQ, RS, TP, PS, QR, PT, ST, QP, RQ, TS} , the vertex with maximum in-degree is ......... and vertex with maximum out-degree is ......... .
- A.
P, S
- B.
T, Q
- C.
Q, R
- D.
S, P
Attempted by 106 students.
Show answer & explanation
Correct answer: D
To find the vertex with maximum in-degree and maximum out-degree, we need to calculate the in-degree and out-degree of each vertex in the directed graph.
In-degree: Number of edges coming into a vertex.
Out-degree: Number of edges going out from a vertex.
Given: V = {P, Q, R, S, T}, E = {PQ, RS, TP, PS, QR, PT, ST, QP, RQ, TS}
Step 1: Calculate in-degree of each vertex
P: Incoming edges are TP, QP → in-degree = 2
Q: Incoming edges are RQ, PQ → in-degree = 2
R: Incoming edge is SR → in-degree = 1
S: Incoming edges are PS, TS → in-degree = 2
T: Incoming edge is ST → in-degree = 1
Maximum in-degree is 2, achieved by P, Q, and S.
Step 2: Calculate out-degree of each vertex
P: Outgoing edges are PQ, PS, PT → out-degree = 3
Q: Outgoing edges are QR, QP → out-degree = 2
R: Outgoing edges are RS, RQ → out-degree = 2
S: Outgoing edge is ST → out-degree = 1
T: Outgoing edges are TP, TS → out-degree = 2
Maximum out-degree is 3, achieved by P.
Therefore, the vertex with maximum in-degree is one of P, Q, S, and the vertex with maximum out-degree is P.
हिन्दी उत्तर:
प्रत्येक शीर्ष के लिए इन-डिग्री और आउट-डिग्री की गणना करने के लिए, हमें दिए गए दिशाकाल ग्राफ में प्रत्येक शीर्ष के लिए इन-डिग्री और आउट-डिग्री की गणना करनी होगी।
इन-डिग्री: एक शीर्ष में आने वाली भुजाओं की संख्या।
आउट-डिग्री: एक शीर्ष से निकलने वाली भुजाओं की संख्या।
दिया गया: V = {P, Q, R, S, T}, E = {PQ, RS, TP, PS, QR, PT, ST, QP, RQ, TS}
चरण 1: प्रत्येक शीर्ष की इन-डिग्री की गणना करें
P: आने वाली भुजाएँ TP, QP → इन-डिग्री = 2
Q: आने वाली भुजाएँ RQ, PQ → इन-डिग्री = 2
R: आने वाली भुजा SR → इन-डिग्री = 1
S: आने वाली भुजाएँ PS, TS → इन-डिग्री = 2
T: आने वाली भुजा ST → इन-डिग्री = 1
अधिकतम इन-डिग्री 2 है, जो P, Q और S द्वारा प्राप्त की जाती है।
चरण 2: प्रत्येक शीर्ष की आउट-डिग्री की गणना करें
P: निकलने वाली भुजाएँ PQ, PS, PT → आउट-डिग्री = 3
Q: निकलने वाली भुजाएँ QR, QP → आउट-डिग्री = 2
R: निकलने वाली भुजाएँ RS, RQ → आउट-डिग्री = 2
S: निकलने वाली भुजा ST → आउट-डिग्री = 1
T: निकलने वाली भुजाएँ TP, TS → आउट-डिग्री = 2
अधिकतम आउट-डिग्री 3 है, जो P द्वारा प्राप्त की जाती है।
इसलिए, अधिकतम इन-डिग्री वाला शीर्ष P, Q, S में से एक है, और अधिकतम आउट-डिग्री वाला शीर्ष P है।