Scribd
Upload
4 views5 pages

Module 5 Notes 2

The document discusses concepts related to graph theory, focusing on matchings, perfect matchings, and edge coverings. It explains the definitions and properties of these concepts, including maximal matchings and the matching number of a graph. Additionally, it introduces the idea of a spanning tree as a form of edge covering in graphs.

Uploaded by

sw224610
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views5 pages

Module 5 Notes 2

The document discusses concepts related to graph theory, focusing on matchings, perfect matchings, and edge coverings. It explains the definitions and properties of these concepts, including maximal matchings and the matching number of a graph. Additionally, it introduces the idea of a spanning tree as a form of edge covering in graphs.

Uploaded by

sw224610
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

es Se M,

natchin
g8, Then
ea. Ela)-e
es, ea, Here
V3
ea
e
graph. the fder Cons kgi-
obvously graph
is
sigle adyacent:A
a
edges
edge chich ein edges 4
Subset
ttUwOo no matching
A
Matching:
main al matoheo g!
no ed¡e is ho
he
matthiog to which
be added
gmaph ca

kg-) Corider Ks
Here any singl edges
2 a manio al mathiog
Egi-a)

two of i% maioal matohia as.


GGnaph and
hese, Hhe maxinal matehings
Among he largest no:c edges ane
wih mathiogs
calledhe lengest mavinal
edges a langes t
The nimb er
maxinal mathisg2celled Hhe
mathing newnber the grph.
Here mathing nmb en a.
Al grgphs dpit tanges t
these
maimal mathings
m- satnated vertex i
Let m be matihing in
&d
tad sad to
gneph a.
bemsatnated edge vn
if Hhene ameage
Dheawise v is
M
n- wnsatunated.

k -
Censider the mathiag
the 9raph below.
e4

Vs

Va e

the venties and e


Then
ae - tuate d,s and vertex

Pentect matching!
Said to be penfect i t
verte d G.
eueny ve
saturetbs
Eg:-t)
e,

Va
Here M, fe,es a perfeet
ymatching
kg:2) Gons idler Va

es

Here m,
ane perfet matehiz
Mi }e, et, ee
Coering:
graph
a a se
edges c sadt
e sud to coien G t evey
vete x ey atleas t
is enadent on
ne edge in g A set edges hat
COVers
graph G sà saicl to be an
edge covering ,a covering subg ap k
sinyply a covering
kg:-) A Ganaph trinally
covering
kg'-2) A Spannng tree is a conmnecad
graph is another coverin9
Egi-3) Censtaer he graoh

d 's
Here
a
covering

You might also like