Graph Theory
Graph Theory is a Aptitude concept from the MPSC syllabus, tested in 3 past MPSC questions (2017, 2019). Below are those real questions with their correct answers and explanations, plus the concepts worth being comfortable with first.
📅 Today's Daily Challenge
Five fresh MPSC questions, the same for everyone today — free, no signup.
Asked in
What you need to know first
Real questions that test this
सोबतच्या आकृतीत A, B, C, D व E या वसाहतींना जोडणाऱ्या रस्त्यांचा नकाशा दाखविलेला आहे. तुमच्या निवडीच्या कोणत्याही वसाहतीपासून सुरवात करून सातहीमार्गांवरून एकदा आणि फक्त एकदाच चालावे लागेल अशा मार्गांची रचना करा. जेथून सुरवात केली तेथेच शेवट व्हावा, ही अपेक्षा नाही. अशा मार्गाची सुरवात किती ठिकाणांवरून करता येईल?
In this road map A and E touch 2 roads each, B touches 4, and C and D touch 3 each. A route that uses every road exactly once must start at one of the two odd-road colonies (C or D) and end at the other, so it can be started from exactly two points.
मी पाली या गावात राहतो आणि मला जवळपास रहाणाऱ्या उपचार करून घेणाऱ्या नेली, तेली आणि सेली या गावातील ग्राहकांना भेट द्यायची आहे. सर्व गावे द्विमार्गी रस्त्यांनी जोडलेली आहेत. पाली ते नेली मार्ग 31 किमी, तेली ते पाली 20 किमी, सेली ते पाली 22 किमी, नेली ते तेली 16 किमी, तेली ते सेली 18 किमी आणि सेली ते नेली 26 किमी या लांबीचे आहेत. सर्व ग्राहकांना भेटी देऊन पालीला परतण्यासाठी मला कापावे लागणारे किमान अंतर किमी मध्ये निवडा.
This is a traveling salesperson or shortest path problem on a graph. By evaluating the given bidirectional distances between Pali, Neli, Teli, and Seli, the minimum distance tour starting and ending at Pali is calculated.
सोबतच्या आकृतीत दाखवलेलां A, B, C, D व E या वसाहतींना जोडणाऱ्या रस्त्यांचा नकाशा अभ्यास।. तुमच्या निवडीच्या कोणत्याही वसाहतीपासून सुरुवात करून प्रत्येकी सात मार्गावरून फक्त एकदा आणि एकदाच चालता येईल अशा मार्गाची रचना करा. ती करताना तुम्ही ज्या वसाहतीपासून सुरुवात केली त्या वसाहतीत परतलेच पाहिजे असे नाही. या बंधनाची पूर्ती करणारे विधान दिलेल्या यादीतून निवडा. Study the map of roads that connect cities A, B, C, D and E as shown in the accompanying figure. Design the route such that you start from any city of your choice and walk on each of the seven routes once and only once, not necessarily returning to the city from which you had started. For a route that satisfy the given restriction, select the true statement from the given list.
The map has 7 roads: A-B, A-C, B-C, B-D, B-E, C-D, D-E. A and E touch 2 roads, B touches 4, while C and D touch 3 each. A route using every road exactly once is only possible when it starts at one odd-road town and ends at the other, so it must run between C and D: it starts at C or ends at C, never both, which is option 4.