Graph Theory — PG TRB Mathematics Questions

5 free practice questions on Graph Theory, out of 25 in this topic, for Post Graduate Teacher Recruitment Board (PG TRB) aspirants. Each one shows the correct answer and a full explanation.

Q1Easy

For a simple graph G with n vertices and m edges, the sum of all vertex degrees equals:

n செங்குத்துகள் மற்றும் m விளிம்புகள் கொண்ட எளிய வரைபடமான G க்கு, அனைத்து உச்சநிலை டிகிரிகளின் கூட்டுத்தொகை சமம்:

  1. an*m
  2. bn+m
  3. c2m (Handshaking lemma) — 2 மீ (கைகுலுக்கும் லெம்மா)✓ Correct
  4. dm — மீ

Explanation

Handshaking lemma: sum of degrees = 2m (each edge contributes 2 to total degree).

ஹேண்ட்ஷேக்கிங் லெம்மா: டிகிரிகளின் தொகை = 2மீ (ஒவ்வொரு விளிம்பும் மொத்த டிகிரிக்கு 2 பங்களிக்கிறது).

Q2Easy

A complete graph K_n has:

ஒரு முழுமையான வரைபடம் K_n கொண்டுள்ளது:

  1. an*(n+1)/2 edges — n*(n+1)/2 விளிம்புகள்
  2. bn*(n-1)/2 edges — n*(n-1)/2 விளிம்புகள்✓ Correct
  3. cn^2 edges — n^2 விளிம்புகள்
  4. dn edges — n விளிம்புகள்

Explanation

K_n: every pair of vertices is connected; m = C(n,2) = n(n-1)/2 edges.

K_n: ஒவ்வொரு ஜோடி செங்குத்துகளும் இணைக்கப்பட்டுள்ளன; மீ = C(n,2) = n(n-1) /2 விளிம்புகள்.

Q3Easy

A tree with n vertices has exactly:

n செங்குத்துகளைக் கொண்ட ஒரு மரம் சரியாக உள்ளது:

  1. an+1 edges — n+1 விளிம்புகள்
  2. bn*(n-1)/2 edges — n*(n-1)/2 விளிம்புகள்
  3. cn edges — n விளிம்புகள்
  4. dn-1 edges — n-1 விளிம்புகள்✓ Correct

Explanation

Every tree with n vertices has exactly n-1 edges (connected acyclic graph).

n செங்குத்துகளைக் கொண்ட ஒவ்வொரு மரமும் சரியாக n-1 விளிம்புகளைக் கொண்டுள்ளது (இணைக்கப்பட்ட அசைக்ளிக் வரைபடம்).

Q4Easy

A connected graph has an Eulerian circuit (traverses every edge exactly once and returns to start) if and only if:

இணைக்கப்பட்ட வரைபடத்தில் யூலேரியன் சர்க்யூட் உள்ளது (ஒவ்வொரு விளிம்பையும் சரியாக ஒரு முறை கடந்து மீண்டும் தொடங்கும்) இருந்தால் மட்டுமே:

  1. aThe graph is bipartite — வரைபடம் இருதரப்பு
  2. bEvery vertex has even degree — ஒவ்வொரு உச்சிக்கும் சம பட்டம் உண்டு✓ Correct
  3. cEvery vertex has the same degree — ஒவ்வொரு உச்சிக்கும் ஒரே அளவு உள்ளது
  4. dThe graph has at most 2 odd-degree vertices — வரைபடத்தில் அதிகபட்சம் 2 ஒற்றைப்படை டிகிரி முனைகள் உள்ளன

Explanation

Eulerian circuit exists iff the graph is connected and every vertex has even degree (Euler 1736).

வரைபடம் இணைக்கப்பட்டிருந்தால் யூலேரியன் சுற்று உள்ளது மற்றும் ஒவ்வொரு உச்சிக்கும் சமமான பட்டம் உள்ளது (யூலர் 1736).

Q5Easy

A Hamiltonian cycle visits every vertex exactly once and returns to the starting vertex. Unlike Eulerian, determining if a Hamiltonian cycle exists is:

ஒரு ஹாமில்டோனியன் சுழற்சி ஒவ்வொரு உச்சியையும் சரியாக ஒருமுறை பார்வையிட்டு தொடக்க உச்சிக்குத் திரும்புகிறது. யூலேரியன் போலல்லாமல், ஹாமில்டோனியன் சுழற்சி இருக்கிறதா என்பதை தீர்மானிப்பது:

  1. aSolvable in polynomial time — பல்லுறுப்புக்கோவை நேரத்தில் தீர்க்கக்கூடியது
  2. bAlways possible in connected graphs — இணைக்கப்பட்ட வரைபடங்களில் எப்போதும் சாத்தியம்
  3. cImpossible in planar graphs — பிளானர் வரைபடங்களில் சாத்தியமற்றது
  4. dNP-complete — NP-முழுமையானது✓ Correct

Explanation

Hamiltonian cycle problem is NP-complete; no efficient algorithm is known for the general case.

ஹாமில்டோனியன் சுழற்சி பிரச்சனை NP-முழுமையானது; பொது வழக்கில் திறமையான அல்காரிதம் எதுவும் அறியப்படவில்லை.

20 more questions on Graph Theory

Track your mastery, build a daily streak, and compete on the leaderboard across all 1 PG TRB subjects.

Practice this topicSee pricing