GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
182 views

Find the matching number for the given graph-

asked in Graph Theory by Active (1.5k points) 13 41 64
retagged by | 182 views

2 Answers

+4 votes
Matching  it means that no 2 edges are adjacent simply a vertex with degree 1

if we have a vertex with degree 0 we say not matched

In the above graph if we start with G we have 2 edges for G In matching we consider 1 edge since if both are considered we get degree of G as 2 so if we consider G-A edge then node 2 is alone and has degree 0 it makes graph to be not matched so we consider G-2 edge , A-0 edge  T has edges with 0 and 1 since A-0 edge is present if we consider 0 then degree of 0 is 2 so we don't consider

we have T-1 edge then we are left with edge E-6

Totally we get (G-2),(A-0),(T-1),(E-6) so matching number is 4
answered by Veteran (14.1k points) 16 63 178
0 votes

The matching number nu(G) of graph G, sometimes known as the edge independence number, is the size of a maximum independent edge set.

and maximum means max beween the minimal independence edge sets,which we can form from the graph.So here  

maximum independent edge set is { (G,2) , (A,0) , (T,1) , (E,6) } hence ans is 4.

 

answered by Boss (6.8k points) 10 48 89


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23356 Points

  2. Bikram

    17058 Points

  3. Habibkhan

    8142 Points

  4. srestha

    6254 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4968 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4298 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3794 Points


Recent Badges

Popular Question Sonali Rangwani
Notable Question Sandeep Suri
100 Club stdntlfe
Nice Question thor
100 Club Vamp thehacker
Popular Question LavTheRawkstar
Notable Question shubham vashishtha
Nice Answer Habibkhan
Good Question jenny101
Regular Ashish Subscription
27,302 questions
35,155 answers
83,985 comments
33,244 users