Scribd
Upload
8 views10 pages

Digraph & Binary Relation Module-4 Notes

The document discusses matrices and directed graphs, focusing on the definitions and properties of vertices, edges, in-degrees, and out-degrees. It provides examples of relations represented as digraphs and matrices, illustrating how to derive these representations from sets and relations. Additionally, it includes exercises for further practice on the concepts presented.

Uploaded by

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

Digraph & Binary Relation Module-4 Notes

The document discusses matrices and directed graphs, focusing on the definitions and properties of vertices, edges, in-degrees, and out-degrees. It provides examples of relations represented as digraphs and matrices, illustrating how to derive these representations from sets and relations. Additionally, it includes exercises for further practice on the concepts presented.

Uploaded by

praveenpraveen94437
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
cAi072q y BuO uONEaT e aq YIPT y uoyL Vv yas auiu uoynjay 2 fe ydrisig uosap se Aqperrojard peyuasasdas aq Ue ys at Matrices and Directed graphs yO . 263 ilcirele or a bullet for each clement 358 A. These circl Of A and label the ci oe . en en ATEN) Ta are called vertices end oes. with the : if and only i les. Draw an a eon of Ris called 8 directed graph cidigapharhs The resulting pictorial se ictorially represented by a digraph, a erie fro * m_ which er pi 1 EN edge, and a ver where areas epi ee ¢ ends is called the e. A vertex which ii ly edge is called ich is neither a source nor a terminus of any edse i é. is call 87, eds ints ‘An edge for whi m mex, An edge for which the source and termi ‘poate Vee ind terminus are ot a aloop, “The number of edges (arrows) terminating at a vertex ‘s tetas sma ® ie in-degree of eax and te number of edges (arrows) leaving a vertex is called the ouferoe -degree of that Jement consider the set A = {a,b,c.d} and the relation R = ((a,b),(b,b),(b,d), (cb), veto Forexample, (ds (da), (0) defined on A. The digraph of this relation is as shown below:’ “s Figure 6.1 at the vertex b. We also see that the in- Observe that, since (b,b) € R, there is a loop the out-degrees of a,b, cd ee of the vertices a,b,c,d are 1,3, 1,2 respectively. Further, ,2,2,2 respectively. As ‘s another example, consider the set A = (1, 2,3,4,5) and the relation i {2,.),0.2).0.4..20 ‘ined on A. The di |. The digraph of this relation is as shown below: 1 2 5. Reta Mtiog, 1 has a Hoop at the vertex I. + Ported the verte tua vate nates at this vertex, We ivy al dge termi ea; e that the a vie ertoX and no edgs 3.4 are [Link] and [Link] rate jeaes th he vertices 1.2. repeat tedegrees: of the R thy ‘oul . sp and let the relation R from A 1p Bhea {1 Qhand B= (pegns “Chey, pr.(2.q (2.9) , pe Wagers ematrir of R. ements of AX B Ww and make the following observation; Hel rat consider al aa (peR (Mek (NER U9 ER NER ple R AMER (ER, 2s) tn view of these and by using the definiti e matrix of a relation, we find th, i tion of matrix ol mie by using the defini | é of these and by given R. jo 1 10) MET 6,4 1 Example 2 87 1,2.3.4} and let R be the relation on A defined by «Ry if and. only if divides x", writen x|y. (a) Write down R as a set of ordered pairs. (b) Draw the digraph of R. (c) Determine the in-degrees and out-degrees of the vertices in the digraph. > (2) We observe that 111112, 113, 114,212, 244.3 )3.4 14 = Hence MSUD.3), 0.3). (1.4, 2.23.24). 8,3, (8) The digraph of & is as shown below, sy 0% A igure 6.3 4 vl trices and Directed graphs fe , ok us | te ing he digraph We note thal, for the vertices 1.9.3 4 , 65 | : nine ely and out-degrees are 4, wees 1.23.4, the in } if exh espective a” e ALL respectively," l-degrees are j Oye? / : | ve Az (1,2.3.4,6) and R be a relation on defined by atts ip \ tent the relation Rasa matrix and dave its ‘and only if a ig i p. Rep R ' 8 digraph, | q Biv 0 i oP gopnition of the given R, we note that : ed 4 ‘ eo eye 1),2,2s (8s Doe 3s (4, 64,2964, 4, (6,19, 66,23.6,3).06, gellhe os vate 6) ing the elements of R, we find that the matrix of R is ing NE ex We : al 6 etd ai 1 0 0 0 Mp3 0 1 0 0 ql 10 10 gi blot cedasnphot Ris as shown below: edi scission IRATE Figure 6.4 rm scribed by the following ra Determine the relation R from a set A 10.4 set Bas described by the f ati: dbo 3 aid 110 Melo 0 1 100 , i that M030, the given My is a 4 x¢ 3 matrix. Therefore AI = 4} and B = {b,, ba, bs), then by observing the elemen's (ay, by) € Ry (aida) # Raby ER (aa, by) € Ry (az. b2) € R, (a2.b3) a (a, bi) ¢ Ry (as, b2) # Ry (age bd € 6 Ret, 266 , (abi) Re (tssbn) @ Re (bs) €R F pf ites Re fannie ee 2 a relation on A whose matrix j EO cad ip may Rand also: by \ y 2 ely yo i 10 oY i £ vii o 1 0 of ¥ ? Maal 10:0 1% e yf ooo 4 2 o11 04 » By examining the elements of the given M(R), we find that” R= (9) (0.2) (Pts (%, 4) (Ws (5 ¥)s (85 2s (V5 1s O42) (2,39, (2,9) The digraph of this relation is as shown below: ~~ ho fe ) & J a y z Fz LN Cy) Figure 6.5 ” 3 oY ' i BEG Fite te reat : | marke ‘on represented by the digraph given below. Also, write downis a o 2D ® Figure 6.6 “The elements of A may be designated a SiBnated 35 a1, a3, ay, ay for the purpose of writing the elements of of writing the elements of R- ices ad Directed graphs es «an / ce ven digraph which has four vertices, we ng, a i sited 0” set A= (1,2, 3,4) and is given by © that the relation 2 re a afi ‘pre- hy B= (1s 2) (1.4) (2, 2), (253), (4,1, (4,4) eno oi o4 Mex 1 19 0000 1004 . 2 (a, byes de, f}, the digraph in Figure below represents a rel 7 associated relation matrix. ee Figure 6.7 ing he given digraph, we find that yexamining R={(a,d)s(b,e), (4,0). (4,0), (0, ko, the matrix of Ris given by 0 10000 ooo 010 000000 M(R) = ' ®=)9 1 1'0 0 0 oo0001 000000 a LetA = (a,b, c,d} and R be a relation on A that has the matrix pe Com en 0 0 blo 1 0 0 ee Metl, 1 1 0 élo 101 he ices. Medlgraph of R and list he in-degrees and ou-aegrees of verter 6. Relay, ea, r ‘ : ning the entries in the given matrix, we find that the given relation > By examining the ssa i following representation as asset of R= (aa, b a (Gr b), (c,) (db), (dd). of this relation is as shown below: ‘The digraph Figure 68 The in-degrees and out-degrees of the vertices are shown in the following Table. Vertex a b c a In-degree 2 3-1 T Out-degree 1 T 3 2 ' ae Exercises 1. Let = {a,b,c} and B = (0,1), and R = ((a,0), (6,0), (¢, 1)} be a relation from A to B. Writ down the matrix of this relation, 2. Let = (1,2,3,4) and R be the relation on A defined by (a,b) € R if and only if a 9s elation doined onthe se 4 2 (6 m7 269, ay ie down they an Matte ang 8 ait ‘ » srmined by each of the diy et elation R deter the digraphs EWen below, Algo, ste oe ®. Wile down the matrix (iy | ZS || © (a) (b Figure 6.9 4.5.7}, and let R be the relation on A hi q waving the matrix. a lio. q Oo 110 Me= “lo 014 1000 Construct the digraph of R. *-Fndthe relation R on the set A and write down its digraph, given tht A = {a,b,¢,d,e} and the g matrix of Ris ectcyo 1100 0]e oo 1 1 oly My=|0 0.0 1 1/¢ 0 1 10 01a 1000 o¢ ‘ ‘Answers a) ‘mel 04 OR 2 4),(4,4)} 2.2) aan Qa va “ syed 13) penn ey eer fae dc oo O° then R= (ay) (tab) (eb) (tsb) ah pe thbb bh pactenn al 5. 4 | Figure 6.11 0 000) émel 9 94 Hevea heed ; Figure 6.12 7%) R= 10.2).2,3),2,4),3,2).(3,3),(3,4),(4,4)} o 10 0 oot Mp = S310 el jo oot

You might also like