Calicut University 2006 M.C.A , - 2K 202 - GRAPH THEORY AND COMBINATORICS (New Scheme) - Question Paper
Second Semester M.C.A Degree Examination, August 2006
MCA 2K 202 - GRAPH THEORY AND COMBINATORICS (New Scheme)
Split by PDF Splitter
C 17328 ....._________________________
a K*S- No--
SECOND SEMESTER H.C.A DEGREE EXAMINATION, AUGUST 3006 MCA 2K 202GRAPH THEORY AND COMBINATORICS
(N<rw Schema) ' '
Time: Three Houna Maximum; iQOMarkx
i
Aruwfir any Five fall (jjiefffioftii.
All quentiofis carry equal inwkf.
1, is) Define ft eutigr&ph.
Prove that ihe sum of degree of att vertices of a graph Q Is twice the number cf edges in G.
(b) Stat wwl piwe Eukr's formula,
2, la) State and prove Kuratowvkft ttnonm.
<~b) Define a HuniJtaciaii gripb utk! pnre that a fruit* connected gr*ph G ii an EvJtriin if and dcJt if eh vertca has even
3, (a) Define trvfc Prove that any me with * Terlicfij bta n 1 m%b&.
(b) Explain the KruskaTs algorithm for finding micjmal spanning: tree.
4, iTl> Explain tho ateps involved in Fluyed-Warehall algorithm,
(W State and prove Mavflaw-Min-Cut the<inem.
5, (a) Find thv numbcrofwayK that un organisation consisting oFSfi i ,L Jibprt Si*n uluiiraeidfint)
Treasurer And Secretary (af&uming no person in t-lectod to more than mo position}.
(h) Prove that t (n + 1 r) = c <rt, r 1) + C r).
6, (a) Find Lbo number of ways that 5 large books. 4 medium sized book* and 3 small books be
placed pc a shrif so thai all books of sune sine are togelhK:
(b) Fmd the number m of triangle* that can be formed hy the ices c/ regular with
n ririm
7, fm} Find the rccurntKS relatM* fatofyrcg aM = A3* * B t- 4W.
<10 Sdlvtf thu recurrence ifJatUft 4dJla 4*.
Attachment: |
Earning: Approval pending. |