Scribd
Upload
3 views58 pages

Chapter 8 (Trees)

Chapter 8 discusses the significance of trees in various fields such as computer science and operations research, highlighting their properties and applications. It introduces key concepts like theorems defining trees, the structure of rooted trees, and the characteristics of different types of trees, including binary and m-ary trees. Additionally, it covers practical examples and applications of trees in data organization and representation.

Uploaded by

kanusoni3456
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
3 views58 pages

Chapter 8 (Trees)

Chapter 8 discusses the significance of trees in various fields such as computer science and operations research, highlighting their properties and applications. It introduces key concepts like theorems defining trees, the structure of rooted trees, and the characteristics of different types of trees, including binary and m-ary trees. Additionally, it covers practical examples and applications of trees in data organization and representation.

Uploaded by

kanusoni3456
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
Chapter 8 trees play an i Sir Arthur Cayley used trees to study the structure impor Portant role in many fields like computer science, chemistry, operations, tc. In computer science, tree: arch ete. INC i trees are useful in organizi . 1a60 arise in theoretical problems such as the Soiree aerate data in data base and analysis of algorithms. 7 get. fq 1 shows trees with one, two, three and four vertices) 3 TS ies © © ® (a) © Fig. 8.1 ite graph in Fig, 8.2 however is not a tree because it contains a cycle abca. Observe that if we remove the edge cb, we get afigaph which is a tree. gy of a fami (cub tributaries) can be represented by a tree. The sorting of mail appear in numerous instances. The genealo A river with its tributaries and subtributaries Fe, decilon Gee Karding to zip code is also done according to tree calles 'sshown in Fig. 8.3. DISCRETE MATHEMATICS (8.2) A collection of disjoint trees is known as a forest A vertex of degree 1 ina tree is called a leaf ora ‘terminal Perot ceare® greater than one is called a branch nade or an internal node. For example inthe fllowing rg 9°** vertices a, h, i etc. are leaves and vertices b, c,d, e are branch nodes. f Fig. 8.4 A tree which is defined as non-cyclic connected graph, can be defined in terms of number of edges and vertices in, given graph. Theorem 8.1.1 Gis a tree if and only if there exists a unique path between every pair of vertices of G. Proof: We note first that existence of a path between every pair of vertices assures that the graph G is connected. Moreover, the graph G cannot contain a circuit if these paths are unique, since the existence of a circuit implies tha there are two paths between a certain pair of vertices. Thus, we conclude that a graph in which there is a unique path between every pair of vertices is a tree. Conversely, if the graph G is a tree, it is connected and hence, there must be at least one path between every paird! vertices in G. Now suppose that there are two distinct paths between vertices a and b of G. The union of these two paths will contain a circuit and then, G cannot be a tree which is a contradiction. Therefore if G is a tree then it has a unique path between every pair of vertices of G. Theorem 8.1.2 Gis a tree if and only if G is connected and has exactly (n ~ 1) edges, where n is the number of vertices inG. Proof: Given G is a connected graph with the total number of edges e = (n - 1), For tree, it is suffices to prove that itis non cyclic. Suppose G contains a circuit C. Let p denote the number of vertices in the circuit € which is equal to the number of edges in C also. by the connectivity of G, we can say that every vertex of G that isnot in C must be connected to the vertices in C Now each edge of G that is not in C can connect only one additional vertex to the vertices in C. | There are (n— p) vertices of G which are not in the circuit C. | Thus G must contain at least (n ~ p) edges that are not in C, Hence, the total number of edges e in Gis given by e * p+ (np) = mwhichis a contradiction to the cn vl i Ba: that G does not contain a circuit and is, therefore a tree, Conversely, if is a tree then by definition it is connected and non cyclic fe have to prove that the number of edges in G are e = (n- 1), prove this result by induction on n. Ww ycETE MATHEMATICS (8.3) TR porn = the result is obvious, uatn> L consider G~ efor any edge ¢ of ¢ |snce a tee is 2 circuitless graph hence, G ~ e's a di | a lisconne | now Gand Gare connected and contain no lected graph with two components G, and G,. : : cycles since | \sGeontinsvverices and edges forte they are both subgraphs of G which is non cyclic. -Jp8y induction QF inj-1, let2 | herefore, the number of edges in G is given by cee % @ = (<1) +(n,-1) +1 2 @ = men-1 yi een-1 | Hence a tree contains (n~ 1) number of edges. | | The results of the preceding theorems can be ‘summarized by saying that the following are equivalent definitions of a tree, dusese That, a graph G with n vertices is called a tree, if Gis connected and a circuitless graph. | (i) Gis connected and has (n - 1) edges. {il Gis circuitless and has (n ~ 1) edges. ir of vertices in G. \n that each of the tree has several pendant vertices. Consider the following tree shown in Fig. 8.5. It has 5 pendant vertices. / Fig. 8.5 It which says that in any tree, there are at least two pendant t ; important resul {| (or Pendant vertices, we have an impor we have (n ~ 1) edges and hence the total degree 2 (n - 1) has to be te of n vertices, ace sinha Sane ‘can be zero degree, we must have at least two vertices of degree one in a tree. among n vertices. F. -1 Eccentricity of a Vertex mn two vertices in a connected graph is a length of the shortest path between them. a that the distance eves sma graph G is the distance from v to the vertex farthest from vin G. Le eccentricity E(v) of a ver &) = maxd we) "nthe following Fig. 86. J gay = EW) = Ee) =2, Es =2 DISCRETE MATHEMATICS (8.4) we Fig. 8.6 the vertex b is the the above Fig. Centre A vertex with the minimum eccentricity is called a centre of G. In t tree. Every tree has either one or two centres. Consider the following tree in Fig. 87. Fig. 8.7 Here Ela) = E(c) = Ele) = ef) on E(b) = Eid) = 2 Hence this tree has 2 centres b and d. 8.2.2 Cut Points es whose removal disconnects the graph. In ay ‘As we have defined earlier, the cut points or cut vertices are those vertice tree, all the vertices except pendant vertices (degree 1) are cut vertices. For instance, in the following tree shom in Fig. 8.8, ¢, d, g are cut points. Example 1: Draw all non-isomorphic trees on 5 vertices. ‘Solution: All non-isomorphic trees on 5 vertices are shown below. JS AN Fig. 8.9 Example 2: Draw a tree with 6 nodes, exactly 3 of which have degree 1. Solution: A tree with 6 vertices which contains 3 pendant vertices is given by Fig. 8.10 ible to draw the sa pe 5 POS ime type of tree with 11 vertices? xs Gwen the tree has 10 vertices. thereto er of vertices of degree 3 inthe rec nas 9 edges Suppose there are x umber af vertices of dearee 1 yu yee xt #10: Handshaking lemma vane (1) A 2e= 5 ai 20 2 2x9 = x43y = 18 = x+3y .@ saving equations (1) and (2) simultaneously, we get, x=6and y=4 Thats there exist 6 vertices of degree 1 and 4 vertices of degree 3 in the tree of 10 vertices. One such tree is shown Fig. 8.12 forthe second part, consider a tree with 11 vertices and 10 edges which has x vertices of degree 1 and y vertices of 3. Hence x+y = 11 ‘No, by Handshaking lemma 2x 10 =x + 3y 8y above equations, we get re B and y= 3 which is impossible. eto draw a tree with 1 vertices which has vertices of degree 1 or 3. Te usc dro cre wi ie vmrins NOD Cap 28 17 has 5 vertices hence, it has 4 edges. Now given the vertices of tree are having degrees 1, 1, 2, 2, 4 e the tree has : ‘he total degree of the tree = 10- 5 8yHandshaking lemma 2e = 4? i ih. ‘bere eis the number of edges in the OP! 2e = 10 = a=5 * he tree has 4 edges. Hence the tree with given degrees of vertices does hat ‘hich is a contradiction to the statement t < DISCRETE MATHEMATICS os) Ry Example 5: Which trees are complete bipartite graphs ? Solution: Suppose T is a tree which is a complete bipartite (m +n), Hence the tree T contains (m +n - 1) number of edges. But Therefore then the total number of veties raph. Let T= Kr, n : thas (mn) number of edges, in, he graph k,n : m+n-1= mn > (m-1)Q-n) = 0 = mel or n=l This means Tis either ky, OF Kp,1 be. Tis a star. Example 6: Find the centre of the following tree in Fig. 8.12. m Fig. 8.12 Solution: The centre of the tree is a vertex with minimum eccentricity where eccentricity of the vertex is the distance fi, from the farthest vertex. The eccentricity of the different vertices of the tree in Fig. 8.12 are given as follows. © (2) =5, e(b) =4,e() =5,e(0) =3, e@) 2+, ef =4eg)=4 eth =3.e()=4 Many of the applications of graph theory, particularly in computer science, use a certain kind of tree, called a rooted tet ‘These trees are used as models for the structures of file directories. Some of the other important uses of rooted trees include the representation and sorting of data, the representation of algebraic expressions etc. ‘A tree in which one vertex (called the root) is distinguished from all the other vertices is known as rooted tree. tt without any root are called free trees or simply trees. A vertex of degree one which is not a root is called a eo external node and all the vertices (including the roots) that are not leaves are called interior nodes. For instance in 8.13 a vertex'vis a root for all the trees shown, Fig. 8.13 The other example of rooted tree is sorting of mail accordi : : : ; ling to the zip code. Consider the Fig. 8.13. The point N i, where all the mail goes out is distinguished from the rest of the vertic of ea "es. Hence N can be considered as the ‘0% of t A rooted trees often used to speciy hierarchical relationships. & example of such a tee, Sn chat ‘a corporation is given in the following Fig. 8.14. which is an organizatio! cast MATHEMATICS (8.7) TREES Prosident General Manager Manufacturing Chiat | Plant Engineer ‘Superintendent Merk ‘Advertsing Domestic International | Supervisor Division Division Marketing Menager Fig. 8.14 Adirected tree (a tree with directions) is called a rooted tree if there is exactly one vertex whose incoming degree is zero all other vertices have incoming degree one. The vertex with incoming degree 0 is known as the root of the tree. In 815 the vertex a is the root of the directed tree. Fig. 8.15 Sir utgoing degree is 0 is called a leaf and a vertex whose outgoing degree is non Be eeenneeds Se arial ool in Fig. 815 the vertices b,c and fare branch nodes andthe vertices d © gare leaves, : Now we are in position to define the level ofa vertex in a rooted tre. Avertex x in a rooted tree is said to be at level n if there is a pa ot length n fom the rot tothe vertex x. The helght of the tee the maximum ofthe ives : Fits vertices, Height of the tree is also called He — oe he ee 2 b . folowing Fig. 8.16, b is at level 1 and g is at level 3. The held 2 (root) Ss, 9 Fig. 8.16 h sexy in gener than the evel fhe vertex, then we sayy i below x. yi below x 'Tooted tree, if the level of 2 ve ‘we say y isthe son of x. Also, xis Said to be the father of y. Two vertices are ato id there is an edge from x to y, then we etn FP = 0 Vy V2 on Yay 9) 1 a path fom x toy, then we sito Se yar tobe van ancestor of ¥. These terms clearly indicate that family trees are indeed rooteq idant of x, Also, x is said t0 DISCRETE MATHEMATICS (8.8) Trees trees. To understand these terms, consider rooted tree Gin Fig. 8.16. The vertex is below Reve cee isthe of cor cis the father of e Also e and fare the sons ofc, Therefore the vertices ¢ and f re i ners. Als the vere cy g are connected by the sequence of edges and g is below c. Therefore, g is @ descen SY Cis ancestor of g The degree of a tree is the maximum degree of the nodes in the tree. In Fig. 8.16, the degree ond nee ed A forest isa set of disjoint trees. If we remove the root ofa tree, we get a forest ie. set of disjoin deleted fr. In another words, ifthe root and corresponding edges connecting the nodes (sons) to the root are OW 2 tree, obtain a set of disjoint trees. This set of disjoint trees is called a forest. “We present now the definitions of subtree and m-ary tree in a rotated tree". In a rooted tree T, a vertex x, together with all its descendants, is called the sul Fig. 8.17 shows the rooted tree T, and its subtree T' rooted at b. a (root) btree of T rooted at x. Folovin, Fig. 8.17 ‘A rooted tree in which every interior node has atmost m sons is called an m-ary tree. =| An meaty tree is said to be regular m-ary tree or full m-ary tree if every branch node has exactly m sons Fo ‘example, in the following Fig. 8.18 G, is a 2 - ary tree or binary tree but itis not a regular binary tree. G,is a regular 3 - ay tree or a ternary tree. S, In a regular m-ary tree, the relation between th en theorem. ; © Interior nodes and the total number of nodes is given by following Theorem 6.3.1 A regular m-ary tree with i interior nodes has (mi + 1) nodes at all, Proof: Suppose the given regular m-ary tree has n number Pet the waar of Wave ox por oha oa ec os out of which there are | interior vertices Since the given graph tree will have total (mi) sons. But root is not a son. Therefore the given tree has a total of (mi + 1) number of Vertice(s), yscRTE MATHEMATICS 43.1 Binary Trees as = vay tees form an important class of saentfication problems and variable lengy gost 2 sons. The vertex to the left of fgit child. Vertex having left child or fame parent are called siblings. A verte tho subtrees. The subtree whose root i oot of the subtree is the right child of a regular binary tree if each internal degree 2 and each of the remaining ver shows @ regular binary tree with root a, th bina hire They are extensively used in the sorting procedure, binary he eae ae mentioned earlier, in binary tree, every internal vertex has ch case left child and the vertex to the right of the root is called its x with no ehik is called parent of both the children, Two vertices having the i She ah cae “ 's a leaf. In binary three no vertex or node can have more than he vere th Of some vertex is called the left subtree of that vertex. Simiary, if the the vertex then the subtree is the right subtree ofthe vertex. binary trees 9 full mam actly 2 sons i.e. in a full binary tree these is exactly one vertex of 's is of degree one or three. The vertex of degree two serves as a root. Fig. 8.19 Fig. 8.19 83.2 Binary Expression Tree Agebraic expression can be conveniently expressed by its expression tree. An expression tree is a binary tree with the following properties: (0 Each leaf is an operand. (il) The root and interval nodes are operators. (ii) Subtrees are sub expressions, with the root being an operator. Here we consider only standard arithmetic operators +,~*,/. An expression having operator can be decomposed into. Fig. 8.20 For example, the expression (2 + (bx€))~ (4% (@% ) oes represented as the tree shown in Fig. 8.21. (2 (2 OQ” O22 % Oo" O-2 © Fig. 8.21 tee em oe ty ie es ee ae DISCRETE MATHEMATICS (8.10) Tey 8.3.3 Conversion of General Tree to Binary Tree oar As we know that for general tree, each node can have as many children as itis necessary to satisfy its requiremens > front atOns. ts required to process general tres, It is considerably easier to represent binary trees in than itis to represent general trees. In this section, the method to convert general tree to binary tee is explained Consider the tree shown in Fig. 822 (a) To convert it into a binary tree, we first identity the branch from the pare, first or leftmost child These branches from each parent become left pointers in the binary tree. They are shown in (©), Then we connect sibling, starting with the leftmost or first child, using a branch for each sibling to its rights, These branches are shown in Fig, 8.22 (c) and they are the right pointers in the binary tree. Now, remove all unnaey branches from the parent to its children, The resulting binary tree is shown in Fig. 8.22(¢). This binary tree is thus obs by connecting together all siblings of a node and deleting all links from a node to its children except for the lnk ty, 'eftmost or first child. This binary tree is formed using leftmost or first-child-next-right-sibling relationship. ® Q Sm wR S © ® ©®© 608060 6 oD (a) The general tree (b) Identification of leftmost or first child (c) Connect siblings (d) Resulting binary tree Fig. 8.22 8.3.4 Full Binary Tree Let T be a binary tree with height greater than zero and with ro Produces two disjoint binary trees, whose roots are level 1 vertices and right subtree of the root ‘a’. The roots of these subtrees are c. which are deleted are called left branch and right branch of 'a' respecti Fig, 8.23. T, is the left subtree with root'b’ and T, is the right subt ;is the right branch of T. B s Lok subtree Right subtree a % Fig. 8.23 ScRETEMAITIEMATICS ae (b) Left subtree (c) Right subtree iy trees using depth-first and breadth-first methods is explained. simplest example of a full binary tree is a single elimination tournament. In the graph of single elimination mmament which is a full binary tree, the contestants are represented by leaves and the winners by the internal nodes tually, there is @ single winner at the root. If the number of contestants is not a power of 2, then some contestants ive byes. The following Fig. 8.25 shows a single elimination tournament with & contestants. Winner (rot) Draw all rooted tree with four nodes, ; ‘ach rooted tree with four vertices rooted at‘ willbe isomorphic to one of the following: eras Fig. 8.26 bampte i 7 nodes. eae Oe Hi ore to one of the following: lution: Each full binary tree will ie 1S. Fig. 8.27 DISCRETE MATHEMATICS (8.12) Example 3: Consider the rooted tree shown in Fig. 8.28. a (Find the father of c and of h. Gi) Find the ancestors of f and of Gil) Find the sons of d and of e. (iv) Find the descendants of d. (¥) How many terminal vertices are there ? (vi) How many internal vertices are there ? (vil) Draw the subtree rooted at e. Solution: ()) The father of cis a and the father of h is c. (i) The ancestors of f are b and a. Also the ancestors of j are d and a. (ii) The son of d is j and the sons of e are k and |. (iv) The descendant of d are j, o and p. (V) There are 9 terminal vertices, (vi) There are 9 internal vertices. (vii) The subtree rooted at e is shown below: Example 4: For the following rooted tree, draw the diagram with the root v at the top and find out whether itis a ful™ tree for some 'm' or not. ES EERE ee MATHEMATICS ge (13) TREES jth the root v at the top, the the given rooted tree: ee can be drawn as shown in ig. 831 Fig. 831 a d-ary tree (because its one internal node v has 4 sons) but itis not full 4-ary tree becouse each internal node is dors not have 4 sons exactly Fjample 5: What is the total number of nodes ina ful binary tree with 20 leaves ? soution: Let n represent the total number of nodes ina full binary tree. Then numbers of internal nodes i = (0-20). mith ‘Ago, by theorem 8.3.1, the total number of nodes in a full m-ary tre is given by Infull binary tree m = 2 n= Qed > n= 2(n-20)+1 n= 2n-40+2 39 Hence a full binary tree with 20 leaves has total 39 nodes, ample 6: Does there exist a ternary tree with exactly 21 nodes ? Solution: Here the given tree isa ternary tree =m = 3, alson = 21 Hence, according to theorem 83.1, n= mitt a2 3e1 = 2 = 3i Fe seve omer ere on sens pce oees Nua ser as we sample 7: if here are 60 contestants ina single elimination tourer: Thow many matches are played ? Sekine A single elimination ourament canbe represented oy 91 Binary tne which contestant represent terminal ‘ces and winners, the intemal vertices. According 0 the problem, there are 60 contestants (leaves). Let i be the number Aneral vertices. Hence the total number of verics= n= 604i Now, by theorem 8.3.1 _ orn= 201 . 59 tournament Hence $9 matches are played in the = re enaplsed aor 10 Ie Information received by the fist person is passed along Leampte 8: A telephone net ratty 3 people, afd each ofthese people calls 3 others, and so on until To mites how fang dest take for a mestage to be relayed frm the fest ono receive the message to ev2y2"" 8 "7 How many people make no calls ? See DISCRETE MATHEMATICS (04) Solution: The given situation can be represented by a tre with a total of 100 nodes, where each node repre. Berson in the telephone network. Also, since each person calls exactly 3 people, hence each node has 3 sons Thee ‘the given tree isa full terary tree. If there are i internal nodes then according to theorem 8.3.1. 100 = 3i+1 = 33 ie. there are 33 interior nodes and thus there are 100 - 33 = 67 terminal nodes (leaves). Therefore 67 persons do make any call. Now, the first person which is serving as the root wil send the message to exactly 3 persons. Also takes § minutes. Hence after 5 minutes, 1 + 3 = 4 people have received the message. Each of these 3 people wil ca sia 3 people After 10 minutes, the total number of persons getting the message is 1 + 3 + 9 = 13. Continuing in the arr aa minutes 1 + 3 + 9 + 27 = 40 and after 20 minutes 1+ 3 +9 + 27 + 81 = 121 persons could get the message a swe have only 100 nodes. Thus it takes 20 minutes forthe message to be relayed to everyone. Example 9: Show that the total number of vertices ina full binary tree is always odd. Solution: We know that in a full binary tree, there is exactly one vertex of degree even (root) and the remaining n ~) vertices are of odd degrees. We know that the number of vertices of odd degree in any graph is always even, Thus in - y is even. Hence n is odd. Example 10: Find the number of leaves in o full binary tree with n vertices Solution: In a full binary tree, the numberof internal nodes iis given by ne diel = 3) en Hence the number of leaves t n~) 02). Hence ful binary tre contains (°) numberof eves. Example 11: 19 lomps are to be connected to a single electrical outlet, using extension chords, each of which has 4 outlet: Find the number of extension chords needed and draw the corresponding tree. Solution: Represent lamps by the leaves and the extension chords by the branch nodes of the tree, Since there are 19 lamps to be connected and each extension chords has 4 outlets, this means the tree has 19 leaves and each branch node has 4 sons. Hence the tree is a full 4-ary (quaternary) tree with 19 leaves. Extension outet Extension chord 1 lem 123456789 0n 2/1 1B 10 13 4418 10 Fig. 032 Now, by theorem 8.32, total number of vertices ina full 4-ary tree n = 4i+ 1, where iis the number of branch nodes z n= 194i But S tie died Hence Polat =, 6 extension chords are required to connect 19 lamps witha single outlet The required tree is shown below Hence, 2 eae go MATHEMATICS 12: Consider the tree as shy te own in Fig, 3 ifthe vertex picked as a root ig eee ee Of the vertices ore cut points (Find alte vertices ot level ‘TREES lution: () We know that every v a sion "Y Vertex of deoreemoreitae : Bato Cone i a cut point in a tre, hence in the given tee, c fu. w, {Consider the given tree with roo Be er pante a5 U. Since the level ofthe vertex i its distance from the root, the vertices of tye take w a5 Oot of the tre in Fig, 86 then, Brample 13: Write and evaluate the expression trees the vertices of level 3 are dst, shown below. Fig. 034 Solution: The algebraic expression given by the expression tree is as follows: (@(@ + aousyy) (m- (aarey-2))) Ws value is (14)- (7) = 7, Sample 14 : Construct the labeled tree of the following algebraic expression: («+ +23) + (9 + &*%) ' Solution: The expression tree forthe given algebraic expression i given below DiscRETE MATHEMATICS Fig. 8.36 Solution: The steps involve in convert the given tree into a binary tree are as follows: 0 Oy The binary tree is shown in Fig. 837 (b). [8.4 PREFIX CODES AND BINARY SEARCH TREES. A Set of sequences is said to be a prefix code if no sequences in the set i a prefix of another sequence inthe 5-7 example the et (1 10,1, 000 O01 refi: code. The set (001 00, 00 mot pet coe mat sequence 00 is a prefix of the sequence 0001. To obtain a prefix code, we use a full binary tee described insecton #3 For a given full binary tree, we label the two branches incident from each intemel node eth 0 and 1. For the le we assign 0 and for the right branch we assign 1. i pastor pes cote agora 708i 14101 cerbe ipeoray trees given By t Zowt a prefix code, ptimal Tree. ny ful Binary tee and let WW, won “ets minimum Seinsance, suppose 3, 4 and 5 are the we a te ‘weGht w(Ty of the tree T,in Fig, 83915 bere 330 optimal tree forthe weights 3 ted ib ae digits, Since different Be binary tree with occ lat of sequence oF nd whch ithe squenceof bes of the edges i the path fro sample Fg, 838 shows fl ray te andthe sequences asigned tot eaves. te above Fig 431 (00,0001, 1 1 tis clear thatthe st of sequences assigned 10 lance isthe length ofthe path ofthe laf rom the root ofthe tree. The full binary tree is called an optimal tree if its tres a ae used in constucngvarbl length Bay Odes, where the eters of he alphabet iy ABC. (01) (10) a (000) (001) rose e ym the root to the leaves in any weight W of -mbethe weights ofthe terminal vertices (leaves). Then, the | ights ofthe leaves in a full binary tree. Fig, 8.28 shows two such binary trees T; ie the weight w (,) ofthe tree tin Fig. 8315 ® 3 q 3 u te Fig. 839 ({,) = 3x24 4x2+5x1=6+8+5=19 (1) © 3x14 4x245x2=348+ 10-22 wT) < wT) 4 and 5. ~ 2) are ted as code of letters have diferent frequencies of oc currence (requenci imum weighted path length (optimal tres) ysl are interpret Bonds toa bi “DISCRETE MATHEMATICS asp 8.4.2 Huffman Algorithm to Find an Optimal Tree itis required to construct an optimal binary tree. The fol Wing Let wy, Wp sons My be the weights of the leaves and algorithm gives the required optimal binary tree. Step 1: Arrange the weights in increasing order. ‘Step 2: Consider two leaves with the minimum weights w, and w» Replace these two leaves and their father bya lea ng assign to this new leaf the weight w, + w, \w,until no weight remains Step 3: Repeat the step 2 forthe weights (w, +), Wy Me Step 4: The tree obtained in this way is an optimal tree for given weights, and stop, 8.4.3 Optimal Prefix Code A binary prefix code obtained from a optimal tree is called an optimal prefix cade, For example, consider an optima, tree for the weights 2,6, 7 and 9 in Fig. 8.40, Fig. 840 ‘The optimal prefix code for the weights 2, 6,7 and 9s given by 000,001, 02, 1) 8.4.4 Binary Search Tree Now we formulate the problem of searching for an item In an ordered lst which arise many a time in our daly lf. To fné ‘person's telephone number in a telephone directory, to find the record of an employee in a company are some ofthe examples of a searching problem. Consider the problem of searching an itern x in the ordered list ks, kr ke where ky ky. ke are given items called Keys. Assume ky < ky < ks. < ke, Our problem is to find whether the given item x is equal to one ofthe keys or eirether x fais between k, and k, for some i. For this, we define a search tree for the keys ky kz... keto be a full binary tre with n branch nodes are kz and the leaves are labelled ko ky kz... ky For the branch labelled ks, ke sate with the label k, its left subtree contains only vertices wit labels < k subtree contains only vertices with labels 2 k. Its convenient to and its right rom ky Ky «ka a @ Foot of the tree. The search, take the middle of the key fr voted in tis way is known as binary search tree. ce, we compare a given item x with the label ofthe root of the tree. Ifx is equal tothe label ofthe eted. Is ess than the label ofthe root then we shall compare x withthe left son ofthe 2% ofthe root, we shall compare x wth the right son of the root. Such comparisons contnut either x matches a key ora leafs reached. Clearly, if leaf labelled kis reached, it me2°S «If the leaf ky is reached, it means that x is less than k, and if Fig. 841 tree constr In the search procedure root, the search is compl and if xis larger than the label 9 until v successive branch nodes U ie fre key, but less than the key her -g MATHEMATICS TREES pe consider the Keys; ky ky and k, wher ey ks and ky and with the terminal nodes ky (a9) ky < ky < ky we construct a binary search tree with the branch oo fy oats shown in Fig. 8.30 where cir coe re ° : er cles denote the branch verices and boxes denote the eaves uppose the Keys Ky, ky ky, ke represent a aicicnanhd ea , ss Present the items CO, EH, GI and PR respectively and the item x = DD is to be agin the given keys. The search steps ac 5 Cording to Fig, 830 will be a follows: fon: compare OD with k= GL sy ky ky and kz. With ky a8 a root, the binary search tree for the ince DD is less than Gl, go to left son of ky and compare DD with ky = CO. yp 3 Se DD ager than CD, Go to right son of, and compare OD with k = EH. 1 since DD is less than EH, go to A sp ice an EH, goto lef son of kn this way, the laf labeled k= CDis reached tun the root, all items in the right subtree are greater than or equal to the root and ech subtree is itself a binary search tree. Fig, 842 shows a binary search tree for key : ON inbrary search tree, any item can be inserted or deleted, toinsert a given itern'k’ in a given binary search tree, first compare the item k with the rot node. heitem k > root node, proceed to the right child and it becomes the root node for the right subtree. Tem k < root node, proceed to the left child, Now, iter kis greater than the node, then the item k is inserted as the Fah child and if item k is less than the node, then the item k's inserted as the le-child Teegltin the procedure, consider the example of inserting inorder the integers 20,3, 10, 22,25, 35, 9, 2, The resulting Bray search tre is given in Fig. 842 Ferdeleting any itern k from the binary search tree, Sted node (k) has no children, then replace the m ‘abe of deleted node with the only child. "édleted node has two children, then replace the "To find the closest value, we mave once to the left and Hen the right as far as possible. This node is called ne ioe cn, Noga acco me tu neg reese ten dete a eraced "de by using + cases, In another words, we find the largest node in the deleted node's left subtree as an. sing previous ca este predecessor. Q we have to consider the number of children of the deleted node (). If ‘ode with null. If deleted node (k) has only one child, then replace the deleted node with the node that is closest in the value to the deleted Ww) ” o DISCRETE MATHEMATICS ___12.__ Q q@ ® Q 2 Soe OMA) Ow w wm (wi) jo) Q @ Q ® &) Fig. 8.43, To understans inderstand the above procedure, consider the following binary search tree in Fig. 8.44, - IATHEMATICS \) gsc (ay = 2 [SOLVED EXAMPLES] ample Obtain the pref code of the flowing fl binary wee in Fig 48 a Fig. 848 solution: Given ‘a’ is the root of the full binary tree. Assign 0 to the left son and 1 to the right son of each branch node of etree Fig. 8.49 ‘he code words for the leaves obtained inthis way are shown in the Boxes. Hence, the prefix code for the given tree is £0.10, 011, 110, 111, 0100, 0101) Example 2 Construct an optimal ree forthe weights 89 20, 11,1315 22 Find the weg fhe ptrna ee Solution: The construction ofan optimal tee forthe weights & 9, 10,21, 13,15 and 22s shown below. 7 4 LN ae : 5 a (0) y 2» A KR aN 2 i, i. é Shee 1 6 2 8 1% © a 450, . 1, ca) / SOR 38 21 oho @ 38 a pees eee fe 2 0 0 @) es gatas 15x36 2242 = 202 is axangngeioxatit™ lf ane 2a DISCRETE MATHEMATICS (02 ‘Example 3: For each of the folowing set of weights construct on optimal binary refi code For each Weight inthe uy the corresponding code word @ 1.23.45,6 9.1012 @ 10,11, 14,16, 16, 21 (id 5,7, 8 15,35, 40 Solution: Optimal binary prefix code for dat 1,2 3,4, 5,6 9,10, 12s as shown below ‘ NX a Bs he 8K a ee . 3 ass Tike Sorat eetgee Cee NE tr oF i” " Vee eee ee ¢ 5 ol cars 6 Bs PSone " 5 aay 0 i: (@) 122 30 22 ecto 2a ca CAN ae An 6 2 2 6 3 4 5 4 5 2 1 e) o fe words forthe leaves are ihc 1 01000 2 01001 3 0101 4 1100 5 1101, 6501 911 10 + 00 12410 gMATHEMATICS he optimal binary pre (@2y q al ‘TREES 2 2 24 ° my & aN o 1 A © the code words for leaves are Fig. 852 18+ 00 10 010 uso 21> 10 145 110 1611 (for the weight 5, 7, 8 15, 35,40, the optimal binay refx code is given by following tre: 2, 3 % 35 40 OB, Oh (08 (0: (no eccl O 2 9 © UGA 8 Oo % B 0 (a) (ha aa alee SY 8 Ea a © 70 3 ° 340 15 8 Std @ o Fig. 853 Th ' code words are er 15 > 100 g = 1010 5 10110 7 101 3520 DISCRETE MATHEMATICS 238 pref code For each weight inthe set gig . construct optimal binary thy Example 4: For the folowing sets of weights, const corresponding code words: 8, 9, 12,14, 16,19 (May 2003, 2005; Dec. 2000, 2003, 2014) Solution: Optima binary prefix code for weights 89,12, 14, 16,19 sas shown in following figure: Code word for8 + 010 Code word for9 + O11 Code word for 12. + 110 Code word for 14> 111 Code word for16 + 00 Fig. 8.54 Code word for19 - 10 Example 5:4 secondary storage media contains information of les with ‘ifferent formats. The frequency of diferent ype, of les i 0s follows 5 (20) bin 75), bat 20 eg 5), dt (4), doc (224 5 28), 9, PP (25), bmp 30), avi (24), pr (29), lt 25), zp a7 Construct the Huffman code for this Solution: () 2 “4 51 0 er Po ** £5239 2 2 oe Fig. 055 ® 78 25 110 142 om 29 4 515s 50 fr Noite % Ue Eye BR aes Fig.256 ) 181 afr. \oes 142 a7 39 87a \b75 % 2 MATHEMATICS a (825) casts 205 ° 8 ‘10 “ Mee 2 tie, & % Fa fy The optimal tree is Mini 09 5 2 4% BRD & % Fig. 859 The Hutfman code for frequency : 20 + 0000 24 0001 25 + 0010 26 > 0011 51010 29 4 0110 30 011 32 1000 35> 1001 75101 37 1100 19 11010 yo > molt ap tne following probably distribution: “nla g EF Goccur wi Sup, co. c D E F 6 ppose data items A, 8. [2 en rm tr mii Sonstuct a Huffman code for the 4 yee a follows: code for the given data ar Solution: The steps involved in constructing the Huffman code for the gi @ 20 1 OF Ole 01. 0 Se 80. BY NB eg) 6.80 @ Fig. 8.60 7) m 2% 20 "% 10, $ 3 5 ( tiv) (cy The Huffman code for the given data is 3 6) Fig. 9.62 05 — 0000 and ooo. 10+ 001 15 + 100 and 101 201 30411 ‘The minimum weight of the tree is 205% 4) +10%3+20%24 The On Sho Ae aate 2 30 A 10 aa (b) (w) 60 30 15 (b) ry tree with Ve se wt tegen sts 0 proce ty 011018) ronstruct @ fll Bina Be ge cae ec ea code if we can 6 sina ful binary ree wth F¥ leaves. BE, a too arb Of tea een vertices ee en nz isSai=n-S 480 ne 2(n-Syt1an=9 ren i246 Pera te tt Diner wit vlan ve tal eres an interior nodes. OF 2 full binary tree is Fig, 8.63 ven assign 0 the lft branch and 110 the ight branch we get Fig. 864 set isin prefix code. sox codes. The give 37, 60, 24. Determine with leaves as re in order 50, 15, 62, 5, 20, 58, 92, 3.8 full Binary tet Since we can construct the generated by inserting integers laample 8: A binary search tree Senumber of nodes in left and right ry search tee in Fig, 868. ‘elution: The steps involved in drawing the resultant binar @ @ Q Q §® Q ® © © © wu ™ " ©) 0 o 4 Q Q (2) (ex @) Q Gg QQ O 6Boe Y De® OO © i © wi Fig. 8.65 w DISCRETE MATHEMATICS (028) Tete, y Example 9: For the following setof weights construct optimal binary prefix code. On, I . 5 oo B o le 1 6 \ 8 ua \ e 20 f Solution : The steps involved in constructing the optimal binary prefix code are as follows 9 0 @ j " s i 626. \ f 8 von 3 Ges Os See tiga Gi) ) , 2 : g 7 no & 2 sue8 Fig. 8.66 ‘The Huffman code for given data 25 (5) > 1110 p@> un y(6) > 110 3) 4 10 2040 [&.5_SPANNING TREES In this section, we study the defini connected graph ceca be any connected graph A spanning subgraph of G which tree is called spanning tree of Ge. 95 che, which is 2 tree and contains all the vertices of Gis called a spanning tee of 6. itis obvious that there can be many spanning tees fora given connected graph Fr instance, consider the ‘graph 1267, two spanning trees of Gare T, and T, jon of spanning tree and the algorithms to find a minimum spanning tree in # jpgraph GinFe ee. ae ‘TREES grt MATHEMATICS (25) 1e edges of G Ec © 8dges of spanning tree T, are called branches of T,. Th coe ite Bip went in Taare called chords of, For erample the branches st Tae ey Gees oy at the Dore re Oa Silat fr the spanning tree Ts of 6 je Fig. 867 the branches of T, are ey ey @5 € and ey an dso T2 a8 br Cu & 200 &y This shows that branches and chow corresponding to different spanning trees a oot Bey crvncied raph G core te Eee mbes ok varkces oR Aig, Thus the numberof chords will be mum Spanning Tree eof vertices and e number of edges. Therefore, its spanning tree will 2) number of edges. Hence, there are total (v ~ 1) branches in any spanning as siven by e~(v=1) 451M ‘gornng tee of @ weighted connected graph Gs fre are nities Vy, Vp. Vy and suppose the envel called 2 minimum spanning tree if its weight is minimum. 19 network of roads or railway lines connecting a numbers of cities. Suppose Cost cj of constructing a direct link between the cities v, and v, are known. The Bese union so ceuon s network tht connec all the station such tat trate ton efean tees Ieee Tispoblem can be represented by a weighted connected graph as follows, ingest each city 25 a vertex of a weighted (yv).Then the connector problem reduces to 9F2ph G and the cost ¢, of building the road as the weight of the edge find 2 spanning tree with the minimum weight in a weighted connected 852 Prim’s Algorithm |ltG= (,£) bea connected weighted graph Construct a minimal spanning tree T for G inductively as follows: Step 1: Take a vertex vain the graph G {va 6} e493 €, = (vn such thats one end vertex vy |Mointhe vertex v, and the edge e, toT ie. T= {Wo vi, fe}. [8893 choose the next edge & | set Step 2: Find the (sin T and its weight is minimum, (\%, ¥) in such a way thatts one end vertex ys nT and the other end vertex y | Bs {should not form the circuit with the edges in ) and the weight of the isnot Age eis a5 small as possible. Adjoin S896 and vertex v to. Ss Repeat the step 3 until T contains all the vertices of G. The set T will Sive the minimum spanning tree of the “algorithm due to Kruskal (1956) is described here to find a minimum spanning rong & <2 euskal algorithm Le Ng = (V8) be a weighted connected graph, Pick up an, edge €, of G such that its weight w (e) is mi 4 19 tee in 2 weighted connected wm, 2: Hedges e, e, «have been chosen, then pick an edge e,.. such that oe for any i= 1,2 k edgese,,e, : "Weight w (e,.,) is as smal es possible subject to condition (i. Stop, ey ee: do not form the circuit. oa DISCRETE MATHEMATICS (8.30) = Few examples which show the working of Prim's and Kruskal’s algorithms (for minimal spanning tree) are itstrayg, i [SOLVED EXAMPLES] Example 1: Find ol the spanning trees forthe following graph. “ le soe Fig. 8.68 (a) Solution: Following are the different spanning trees of the given graph. : a Jo a a ] | ie c | | el a >! tee be Pa Vv N. aS an ] = Fig. 8.68 (b) Example 2: Find the minimal spanning tree for the following graph by using Prim's algorithm. 3 Fig. 8.69 (a) Solution: Starting from the vertex a, the minimum spanning tree of the given graph can be obtained by using Prins algorithm as follows: a a a of 7 y 2 Be tegaco’ bo 1 q ' ° 0 @ ®) « 6) Fig. 8.69 (b) The graph T obtained in step 5 is a minimum spanning tree. Its weight is 7. Example 3: Use Prim's algorithm to construct a minimal spanning tre fo the weighted graph tn Fig 70 staig ont vertex a Repeat the process starting from the vertex, Verify that both tres have the some weight ss MATHEMATICS (0.31) it he help of Prim algorithm, ty IMUM spannin ise Panning tree ofthe graph in Fig. 871, stating from a is glen © Fi. The total weight of the minimum spanning tree is 1 Now use the same procedure, starting from the vertex b Fig. 872 The total weight ofthe above minimum spanning te is also 12. Hence both the tees obtained in Fig. 873 and '5872have the same weight. ample 4: Use Kruskal algorithm to find @ minimum spanning tre forthe groph shown in Fig, 8.73, DISCRETE MATHEMATICS (8.32) Solution: The minimum spanning tree by using Kruskal’s algorithm is given in following steps: vy A ry a) Ne, acy ; @) Fig. 8.74 Now at this stage we cannot take any edge from G because otherwise edges will form a circuit. Hence the graph, Fig, 874 isa minimal spanning tee é Example 5: Determine « minimum spanning tee forthe graph shown below. (Dee. 2014 bia guia “ a Fig. 875 Solution: Using Prim's algorithm we obtain a minimum spanning tree forthe given graph as follows: (1) Os (2) a (3) & p oJ as NU a © 8.76 ee Tis a minimum spanning tree forthe given graph. Its weights 23. for Fig. 872. The above Beample 6: Find te minimum spanning tree ‘TREES HEMATICS ee 3» an the nee F Prim algorithm, the min Bevan ca yw geen snow Po 7H nee ee Jon se 1 A mcs 6 og al ® Fig, 8.78 ‘a minimum spanning tee. Its weight is 13 TegaghT shown in Fig. 8:78 um spanning tree for the graph shown in Fi ample 7: Obtain the minim orning tree. 879. Obtain the total cost of minimum Fig. 8.79 rn spanning wee obtained as follows: tion: Using Kruskal algorithm, the mi Y, s @ 4 a e ° The graph Tis a Example inimum spanning tree of the given graph. Its total cost is 40. ve the stepwise construction of minimum spanning tree forthe following graph using Kruskal ‘algorithm, A 10 = Using Kruskal's algorithm, the minimum spanning tree can be: obtained as follows: 4 i ro—2 op a Ny @ o a ho fe ° Solution: The minimum ee S s “ « - wis 5 The above tee Ti 3 minimum spanning te for the gue" 884 ven GFE. Its weight ig 24, ing Prins algorithm, the minim sng 0 '¢ minimum spanning tre can be obtained as shown in following steps: ons a) @ a o 6 ” ~O g ® 25] Fr) @ @ © © © o aq 0 7D © ® ® a | 25 le = 25 @ ® @ © Doe oy? Fig. 886 ‘ete Tis a minimum spanning tree with weight 99. FUNDAMENTAL CIRCUITS AND FUNDAMENTAL CUT SETS aga iis secon, we describe the inte relationship between spanning tres, cycles and cut sets. InGir a cnmected graph and lt Tbe a spanning wee of. Consider a chord of T Lean edge eof G whic is not fh rt The'T + e contains a unique circuit called fundamental ‘cireult of G with respect to T. A fundamental circuit in a graph Br cas asec ta spannig te of ren sparring toes ofthe graph Ge hncumsned eae tiene For example, in Fig, 887, T, and T, are two spanning tres 2 connected graph 6, a o/\\e of \w eed onion ° hs e g 1 ts Fig. 887 du ute chord ted 10 T then we obtain a cout ty ey «Tis @ ending toe, the fundamental circuit of G in T, is (@, @y Noy a ruit coroner’ ae igre 00 & Fe the frame eat yt and in fer the spanning tree 12° sqm above It's ‘lear that diferent spanning trees have different fundamental hada fundametal re any spanning en ea) the number of chords of that spanning tree *Spalad of fundamental a Sumber of vertices ‘and e number of edges then the spanning tree T has (v ~ 1) Noy psrneied oma me chocds TS there willbe (@ = ¥ + 3) number of fundamental circuits in G with (e=v + 1) nu *ethe spanning tree fay, the ed G are chor eee ens similarly corres DISCRETE MATHEMATICS (6.36) Ts Fundamental Cut set Me have ready discussed abou cut setsin a connected graph in chapter 7. The cut sets related to he spanning connected graph are defined below. - Let be the spanning tree of the connected graph G Since the removal of any branch fom a spanning tre bray sparing ee nt two tes, we Sy that coresponding to a rachin a paring ee theres usenet the graph into two subsets corresponding to the vertices in the two trees. It follows that for every branch in » see tee share comesponding cut set ale fundamental cut st, The set ofa fundamental cit sets ofthe gaph ot £EePeet go the spanning tee Tis called a fundamental system of cut set. For example, forte following graph @ sho fi. 88 The removal ofthe branche rom the spaning tre T Fig. 888 divides the vertices of Tinto we subsea” 4} an 6 fe 6 T Fig, The number of fundamental cut sets is equal to the number of branches in the spanning tree. If the connected graoh 6 hhas v number of vertices and © number of edges, then the spanning tree has (v ~ 1) branches which is the same asthe number of fundamental cut sets. Now we present a close relationship between the fundamental circuits and the fundamental cut sets relative to a spanning tree. | Theorem 8.6.1 |_Acut-set and any spanning tree must have at least one edge in common. Proof: ‘Suppose there is a cut set that has no common edge with a spanning tree, ‘Then, the removal of the cut set will leave the spanning tree intact. ‘This means that the removal of the cut set will not separate the graph into two components, which isin contradiction 10 the definition of a cut set Hence, there must be at least one edge common between the cut set and the spanning tree of the graph, Theorem 8.6.2 ‘A circuit and the complement of any spanning tree must have at least one edge in common. Proof: We know that the complement of a graph G is @ graph whose vertex set is same as the vertex set of 6 and which ot in G. tains the edges which are m : Ts ‘the complement of a spanning tree will contain the edges which are not in the spanning tree. ined i If there is 8 circuit that has no common edge with the complement ofa spanning tree, the circuit should be contains" ing tee, ‘4 tae aa ic impossible as atreecennot contain circuit However it and the complement ofthe spanning tree must have at east one edge in common. Hence,a cit Lt MATHEMATICS yscRETE {ean TREES 863 Georem Jeera given spanning tree, let p = (1 ep, [ors fe SPanTING tree. They °° 8) Be indomen tained i 5-5 ore |oreover exis Not contained in any other fungi” te fund ack proof: eee 19 to the chord e, 218 common in both and, ow C contains branches of the spanning tree and the eno de; and D contains the chords @y ey. ¢ and the branch % Be SM Sever uns of sigs common wa era er Jitreore C and D will have an even number of edges in common and ¢; is the only other edge that can possibly be in both C and D. /thus e; must be contained in ¢ Cut-set in which @, is a branch and e,, lamental circuits corresponding to e, for i {etc be the fundamental circuit conesponain since D also contains e,, hence, |Simiar, it can be shown that e, is contained inthe fundam |oterfundamental circuit To prove this, suppose C" is a fundamental circuit corresponding to a chord notin D. C: cannot contain e,, because stherwise, Cand D will have e as the only edge in common, rental circuits of eye, .. €,. AlSO, e; is not contained in any [SOLVED EXAMPLES] Example 1: How many fundamental cut sets and fundamental circuits are therein a graph G (with respec any spanning tee with 8 vertices and 11 edges ? Solution: Since the graph G contains 8 vertices, hence, is spanning tree T will contain 7 branches. We tow that ‘emesponding to each branch of the spanning tree T, there exsts a unique fundamental cut set. Hence, there are Aindamental cut-sets of G with respect to. ee oes with espect to T re are 8 fundamental cuits in G with respect to eres a unique fundamental circuit, hence there are Banpie 2: rind ae endamertlcets ofe flowing GDh 6 wih rep he gen Spanning Was F shown : Fi Plowing Fig. 8.89 below. T (Spanning tree of G) Fig. 089 ee The chords of Gare ey ey, and ey Hence, there wil be four Plt: 0 6 0 anise tse inl The branches fT 6 0 guna mental circuits, Corresponding *0 °* p “ponding to the chords ey & ap * 4 the fundamental circuits are ) respectively 2 Cy, es, (7 Cru & DISCRETE MATHEMATICS (6.38) Tees ning tree T. Example 3: Find the fundamental cut-sets ofthe following graph G with respect to the given spanning Fig. 8.90 Solution: Corresponding to each branch of the spanning tree, there exists a unique enero Set. Here the spanning tree T has 3 branches e,,e,,e,, Hence the graph G has 3 fundamental cut-sets with respect to T. For e,, (@,, 3) is a fundamental cut-set. Fore; and e,, (@,,€3} and {e,) are fundamental cut sets respectively. Example 4: Find the fundamental system of cut set forthe graph G shown in Fig. 8.91 with respect to the spanning tree T. (Dec. 2014) Solution: Here the spanning tree has 7 branches and corresponding to each branch there is a fundamental cut set Hence there are 7 fundamental cut-set of G with respect to T. Different fundamental cut, sets are given below: Branch name Fundamental cut set & 3 feey es) & ley ened Bs les ey ep) & ley eyed 0 > ie ee & ex) en fen 6) es > ey ext Example 5: Determine al posible spanning tes ofthe given graph shown in Fi. 882. Consider ony Se aa fundamental system of cut-sets. gc85TE MATHEMATICS potion: A POSSI SPaNNNg tre ae shop» : (839) follows 3 a A & ® 6) © 2 2 2 > ba D8 es a ° he eG e 4 ea fee 2 ° ° (10) oy (12) c Da bite ° > a cr oe a efi e (3) 14) 18) (8) Fig. 892 (b) Now, consider the following spanning tree T ofthe graph G in Fig, 893 The fundamental cut-sets with respect to Tae as follows, ANG ° ° “ © 1 Fig. 893 Branch Fundamental cut-set > Levey ey er) 2 teed & > levered > (ee en6) ‘fundamental system of cut-sets: in Construct a spanning tree of the graph G and find sets of the graph G in a Fig. 8.94 6: Determine all possible cut-sets of on DISCRETE MATHEMATICS (040 They Solution: A cut-set is a set of minimum number of edges where removal disconnects the graph. Following are y, possible cut-sets of G ~ (D) fey 2h (2) (ey ey eg) (3) (ey, ec) (4) (0s, ee), (5) (0g, Crh, (6) (€p Cy @sh (7) (Cx Cy Cx) (8) (0p Cy Cs), (2) fey ey ee), (10) fey, €y @), (11) fey eg), (12) (6p 4) (13) (@y €y) (14) (@p€y @7h (15) (€y @y Now consider the following spanning tree in Fig. 895 The fundamental cut-sets are Branch Fundamental cut-set > eed > ney ed) > (eed > ey 1 > ered Example 7: Prove that the complement ofa spanning tree does not contain a cut-set and that the complement of cust does not contain a spanning tree Solution: Suppose the complement of a spanning tree contains a cut-set. This means, the spanning tree does not contain the cut-set. Hence there is no edge common between the cut-set and the spanning tree. But this is the contradiction t9 the theorem 861 that there is at least one edge common between a cut-set and the spanning tree. Therefore the complement of a spanning tree does not contain a cut-set. For the second part, again assume that the complement of a cut-set contains the edges of spanning tree, This means there is no edge common to the cut-set and the spanning tree, which isthe contradiction to the theorem 8.62. Hence he complement of a cut-set does not contain a spanning tree. Example 8: Draw the fundamental cut-sets and union of edge disjoint fundamental cut-sets of the graph G with respect spinning trees T, and T, given below. 6 5 & os = 4 os oe 6 1 % Fig, 8.96 _ ge MATHEMATICS The fundamental cutsets wih ets Branch e oe es a e. y = te, eg o fs for the spanning tree T, eee Fundamental cut-set a = tee) ns & & es) fepeped em Pee ee “(oan The union of edges disjoint fundamental cutsets it fey & e €3) A 9.897 ital circuit. | ample 9: For the Fig. 8.98 shown, give funaaments ic 2 . * —S ( 4 . Fig. 898 | | ™~ DISCRETE MATHEMATICS: (8.42) mm Solution: Since there are four chords ey ey €y there wll be four fundamental circuits corresponding to each eho “ Chord Fundamental Circuit e er) & fea €5 &y @3} es (es, & 60 e (epee) Example 10; For the graph drawn in Fig. 899 (a) and spanning tree in Fig. 8.99 (b), determine fundamental system g sets and fundamental circuits. ut Solution: Since there are 4 branches in the spanning tree (b), therefore there will be four fundamental cut ses corresponding to each branch. Branch Fundamental cutset e> {ey 5 €) os {ea €7,€3} & {ey G5, p, Cy Ooh ee fey ey eg) Since the spanning tree contains 4 branches, the remaining 4 edges in the graph are chords, namely el, e4, €5, e7 Corresponding to each of the chord, there is a circuit called fundamental circuit. They are given as follows: Chord Fundamental circuit e& > (ey erened & > f{euereced & 7 (ered & 7 (e,e0e) [exencise 8.1], 1. Draw all non isomorphic trees with 4 and 6 vertices. 2. Drawa tree with 16 vertices which has either degree 2 or degree 3. Can you draw such a tree with 15 vertices. 3. Is it possible to draw a tree with six vertices having degrees 1, 1, 1, 1, 3, 3. Fyes, draw the tree. 4. (a) Define - (i) Rooted tree, (ii) m-ary tree, (ii) full binary tree, (iv) level of vertex the rooted tree, (¥) Subtree and regular tree, (iv) Regular m-ary tree with example. (b) Find the cut points of the following tree. Also find the level of each vertex. pa HT 8 wth terial vets ad itera vere. capain he following ferns in a rooted tree = gen (o parent i) Subtre® Ov) ancestor (1 descendant Answer the following question forthe tre in Fig, 8101. ed the parents of fand of fed the ancestors of cand d ay Fd the descendant ofeand of oy Draw the subtree rooted at « Fig 8202, 4 Find whether the fllowing tree isa full mary tree for some m or not Find the height of the tree. Redraw the tree withthe root'V on the top. ig 8102 a, Otte te otal number frees ona binary ee wth Sines nodes. [Link] nae tenes ena te wh 2 ere. ag ME fll ary tree wth 100 nodes ? . iets tia binary prefix code Se flowing set of weghts, const an optimal binary pref code. For each es op eeding codeword eight in the set. sive the 2357913. vu 89.20/21 35.15 22 "2 spanning tree in a connected graph When iit called minimum s & c 2° lar oda minimum spanning te na weighted conne Panning tree, ted graph, Rees ae a the total cost of the minimum spanning treg va gas Fe 0 wi Fig. 8.104 17. Define the terms cut-set, fundamental system of cut-sets and fundamental circuits, 38. Determine all possible cut-sets of the followin 19 Sraph shown in Fig. 8.205. Construct a spanning tree of the graph G ‘and find its fundamental system of cut-sets 19. Find the fundamental system of cut-set for MATHEMATICS poet (8.45) Tatts a given spanning tree, j ear ee cern 4) be a fundamental circuit in which e, isa chord and ey €3 ~ @ a7® Bec Pactiog UeelProvs thet & esting im the fundamental cut-sets corresponding to «for |= 2, 3,~ k Moreover @; isnot contained in any ther fundamental cut-set a1 Prove that a regular mary tree with intersy 2 Witea short note on “Binary Search tree and 23. Define prefix code. odes has (m,+ 1) nodes at al its applications Justify whether given set of codes are prefix codes or not ( (000, 002,02, 10,23, (i) 2, 00,01, 090, 000, 1H Define: ( Forest (i) Height of tee, i) Ordered tee, (vy Properties of tee. [ANSWERS - @.1] 1. Nomrisomorphic trees on 6 vertices ae pm Fig. 8.107 Non-isomorphic trees on 4 vertices are: Fig. 8.108 2 Tree with 16 vertices of degree 1 oF AR Fig. 8.109 1s degree 1 or 3. draw a tree with 25 nodes which has deg tis not possible to 3 7am Fig. 8.120 fT are given below: 4, The vertices of degree other than one are cut vertices. Levels of vertices of Ud) = 1) = 1 Ue) = 0g) = (= Lim) = 2 Ud) = ((e) = 1th) = 11) = 1) = Lin) 5. height 6 Fig. 8211, 7. @ candd (i) aand b (ii) f and (h, i) (W) The subtree rooted at cis ‘ ® 9 7 i Fig. 8.112 8. No. itis not a full m-ary tree. Height 3, 91 10. 61 un. No, the integer solution to the equation 10, 13. (0 Code word for 2 0000 Code word for 3+ 0001, Code word for 5 + 001 Code word for 7 +10 Code word for 9-5 11 Code word for 13 + 01 0 = 4i + 1 does not exist | xs MATHEMATICS 16.0 tun ae Weight = 48 } «) i Fig. 8.116 Weight = 18 18. All possible cut-sets are {e,, €, €) {ey €y Ed 1p € {8a €y En fey €> ee), {tu Cy & el 1 ty by 03) oy ep (Cy ep On Oa fC €5 €, 05 03, {ey €5 p&p €shley ep &y &y €3h (8, &5 ey € &d) 19. fe, @3), {ey €y €3) fy @ @3) BZTRANSPORT NETWORK Inthis section, we will see how a weighted directed graph can be used as a model for a network of pipelines through ‘hich some commodity is transported from one place to another. A newotk represents @ model for transportation of 2 commodity fom is reduction centre to is market trough conmunicaven nartes such as roads, pipelines, cables, et. tis important to know the maximum rate of flow that i Possible from one place to another place in the network, This type of network is represented by a weighted connected graph in which the vertices are the places (stations in the network se the edges are lines through which the Scots gus, matey crs ac) fm. The weight aa poe number aoced wih ach ede represents i Jrnam amount of ow possible per unit time. The graph shown in Fig, 8101 Capacity of the line, that is, the max! ‘and 10 lines. The capacity of each line is also indicated inthe Fig. 8.17. ris a flow network containing 6 stations and 20 lines. Me cAP. Fig. 8.117 eigeis called 9 source s and the vertex with no outgoing edge i called @ 9 -oring ry “ intermediate vertex hk the total rate of commodity entering is equal to the & f DISCRETE MATHEMATICS. (o48) Tress commodity leaving the vertex ie. there is no accumulation or generation of the commodity at any vertex along the wa Further, the flow along any edge cannot exceed the capacity of that edge, i Now we define the transport network and maximal flow. Transport Networ simple, connected, weighted, digraph G is called 2 transport (or flow) network if the weight associated with every directed edge in G is a non-negative number, In a transport network this number represents the capacity of the edge and is designated as C (i) for the edge directed from the vertex ito the vertex} ‘Maximal Flow: In a given transport network G, a flow isan assignment of non-negative number f(,j) to every dircteg ‘edge (}) (edge from the vertex ito the vertex) such thatthe following conditions are satisfied: () For every directed edge (ij) in G, fis ch) (i) There is a specified vertex s in G, called the source, for which SfD-S fis) where the summations are taken overall the vertices in G. Quantity w is called the value of the flow. There is another specified vertex tin G, called the sink for which, (iv) Allother vertices are called intermediate vertices and for each intermediate vertex j Sfijp= StGH jest i k tis clear from condition () that the flow through any edge does not exceed its capacity. Conditions (i) anc (i state that the net flow out of source and the net flow into the sink is w. According to the condition (Ww), the amount of material fiowing into a vertex must be equal to the amount of material flowing out of the vertex except at the source andthe sink For a given flow, an edge (i) is ssid to be saturated i (= c(,)) andi said to be unsaturated iff.) <¢(i.) ‘A set of flows f (forall (i) in G is called a flow patter. A flow patter that maximizes the quantity w is called * mayimal flow pattern. There may be more than one maximum flow in transport network. Cut and the capacity of 2 cut Ignoring the directions of edges in a transport network, consider a cut-set with 5 te the vertices sand t that is 2 cut set which separates the sources from the sink t, Such a st of edges in a wanspot pect alled a cut. The notation (P,P) is used to denote a cut that partitions the vertices into two subsets P and network isc nee the subset P contains the sources and the subset contains the snk The capacity ofa cut denoted by C %) ie defied tobe the sum ofthe coacties of those edges directed frm the vertices inthe set Po the vertcesin tas c@Py= Ss cd ieP ie? in Fig 8.128, the dashed line identifies a cut that separates the vertices P = (sb) from the subset of vertices For example, 4 = (dt the capacity of this cutis 5 +15 +3 i: On el aaa ere MATHEMATICS ose (249) ‘TREES Fig. 8.138 theorem 8.7.1: ewok [Theorem 8.7.2 (Max - Flow Min - Cut Theorem): he value of the flow w ina given transport network i less than or equal to the capacity of any cutin the na given transport network G, the maximum value of a flow from the source s to the sink tis equal to the minimum vale of the capacities of all the cuts in G that separate the source s from the sink t for example, consider the transport network of Fig. 8.117. Ithas eight cuts that separate s from it. These cuts and their | capacities are given in the following table. | Tobie | Vertex set P Capacity ¢ (P, | o 10 | Gb) 4 | sd a | | co) 9 | be 2 | {s.b,d) 2S 6c a Gres Res aie rary sno weet A {b, 6 th The maximum flow possible ins to tin | ‘henetwork is therefore w = 9 units ee igo x creme mesoer iow h 3 teen network. According to the 3 Ve will now present af ‘transport network is {ess than or equal to the capacity of any cut. Therefore, we can Eo c flow, see oe being procedure nthe even network fo find the maxi d Meorithm: ‘each edge is given. che given network. Also assign the label (- «) tothe source the source s Suppose the vertex bis acjacent to sand ¢(.b) > f(b) =f (5b). The vertex b is not labeled if b) = f(5 6) nthe copacty of f © tnt i flow to each ecg illy, assign the zero ea ake Sen al hore verces whieh ae I ay «Cts then label the vertex b 25 (2° spose a transport network wit DISCRETE MATHEMATICS (8.50) Trees 3. Scan those vertices which are adjacent to labeled vertices. Suppose the vertex 4 eee ae labeled vererb)] The vertex q is labeled (b+, Aq) where Aq is equal to the smaller of the two quantities Ab and [¢ (b, 4) ~F (bq) it¢ | (6, q) > f(b, q). ‘The vertex q is not labeled if ¢ (b, q) = f (b, q). Also the vertex q is labeled (6, Aq) where Aq is equal to the smaller of the two quantities Ab and f (q, by (q,b) > 0, The vertex q isnot labeled if f(g, b) = 0 Such a labeling process is not unique. The vertex q might be adjacent to or from more than one labeled vertex. n such ease, when a vertex can be labeled in more than one way, an arbitrary choice isto be made Repeat the step 2 (labeling the vertices that are adjacent to or from the labeled vertices) till we reach to the sink 4. Ifthe sink tis labeled with the label (y*, at) where y is some labeled verte, then increase the flow of the edge iy 9 | from (yt) to f(y, t) + 4 t. Note that the vertex y must be labeled either (qt, Ay) or (7, By) with Ay + At for some vertex g Ify is labeled (q*, ay) then increase the flow in the edge (ay) from f(a, y) to f(@,y) + At. On the other | hand, if y is labeled (q~, Ay) then decrease the flow in the edge (y, q) from f (y, @) to f(y, q) ~ At. This process is continued back to the source s and the value of the flow inthe transport network will be increased by amount at ‘Again stat the labeling process to further increase the value of the flow in the network ie. goto step 2. | | 5. Ifthe sink tis not labeled, then denote all the labeled vertices by P and all unlabeled vertices by B. Determine the | | capacity of the cut (P, B) which is the value of the maximal flow. j Now we illustrate few examples. Example 1: Determine the maximal flow in the following transport network > Fig. 8.119 Solution: Step 1: Assign the flow zero to each edge and the label (-, =) to the source s, Fig, 8.120 Step 2: The vertices b, ¢ d are adjacent to the source s. Therefore, we label the vertices b, cd. For the vertex b,c (& b)-f (5b) =2 _ggsTE MATHEMATICS rrsthelabel of the vertex is i, 2 St TREES similarly the labels oF ¢ and d are ict Mand 6% Now the sink tis adjacent to both the vertices b and d. So we can choose any vertex bor for labeling of sink t. Let uschoose the vertex d. For the vertex d, the label is (s*, 3) and €(d.)-F(d,) = 5-0 = Minimum of 3 and 5 is 3 and thus the label of sink t will be (d*, 3). According to the label of the sink, adjust the flow inthe edges (4, t) and (s, d). Fig, 122 Repeat the step 2. In each pass the new value of the flow is obtained. Step 3: 2) Fig. 8.123, DISCRETE MATHEMATICS, (052, ra Step 4: From the step 4, its clear that the maximum flow is 7. Example 2: Soive the following network problem (Dec. 2014) Solution: Different iterations for the maximum flow are given as follows: x: ~~ bis’,2) Fig, 8.126 (@) (853) TREES ao in ce." step 2! Fig. 8.127 ole.2) ig. 8.28 The maximum flow is 13. Trample 3: Use labeling procedure to find a maximum flow in Determine the corresponding minimum cut Raha, The wansport network shown in the following figure (Dec. 2014) 7 Fig. 8129 Selution: To find the maximum flow inthe ge" transport network assign the flow zero to each edge and label (- =) to the source a. Step 1: Fig. 8.130 e source atl st erefore label the vertices b and cas (a, ab) and (a+, Step 2: Since the vertices b and care a “respectively, where ap cB ecm ao w -fle.b) =3 p-fed =? Label of bis a" 3) and label ot DISCRETE MATHEMATICS (054) Trae | Now, the vertices d and e are adjacent to labeled vertices b (a, 3) and ¢(a°, 7) therefore, we label the vertices ang as (b*, Ad) and (c", de), where ‘Ad = min (ab, € (b, d)~ f(b, d)) = min (3, 5,-0) ad = 3 ‘Similarly, e = min (ac, C(c,e)-F (ce) = min (7, 4,0) ae Label of d is (b*, 3) and label of e is (c’, 4). Now, the sink z is adjacent to both the vertices d and e, we can choose any vertex d or € to label the sink z Let y, choose the vertex e, which is labeled as c+, 4). The label of z will be (e+, Az) where az = min (4,3,-0) az=3 Hence, label of 2s (e, 3) Sa lal ol vehiced cen ba showers GIGWE According tothe label of the sink z, adjust the flow in 3) 3) the edges (2), (4 @) and (2. » ) gd Fig. 8.132 Repeat the step 2. In each pass, the new value of the flow is obtained. 1 adjusting the flow, me have eee 7 (5,3) g ¢ Adjust the flow according to sink label. : eS ss MATHEMATICS ice the VeTeX 2 (Sink) cannot bg (8.55) ‘TREES label 6 BPBrORChng to vertons fe MPEG, we have 9 'S Are Saturated or the eqa oP, The vertices b d and z cannot be labelled because either ‘Se5 in the opposite direction have flow zero. At this stage, we we . ve riimur cut (PB) (Pis the «4q) he edges in cut PP ((a, by, sence the maximum flow in the Fig. 8.139 (c) 2) 15,15) 9 DISCRETE MATHEMATICS. (056) Trees Fig. 8.139 (h) Fig. 8.139 (6) Since z cannot be labelled, we will stop. Minimum cut = {(¢ (fe), (2 The capacity of cutis C (ce) + Cif, e) + C(d.2) = 6 +6 +20 = 32 The maximum flow in the network is 32. The saturated edges are (a,b), (bd). (4.2) (2, (6 e) fe) Unsaturated edges are (a,c) (c.f. (fd). (fb). (a, (@.2) ‘Example 5: Find maximum flow in the transport network using labelling procedure. Determine the corresponding minimum cut. 3 Fig. 8.140, The maximum flow in the transport network using labelling procedure can be obtained using following steps @.5) 4) Fig, 8.145, Since Z cannot be labeled so we have to stop. The minimum cut is BP where Pis set of labeled vertices and isthe set of unlabelled vertices P= {@bodh), P= Edges in cut PP = {(d, 2) (h 2) Capacity of the minimum cut C (d,2)+ C (hz) =5+6= 12 Maximum flow in transport work is 11 EXERCISE - 8.2] 1. Explain the terms: (Transport network, (i) Capacity of a cut, (il) Maximal flow. 2. Find the maximal flow in the following network anaes Fig. 8.46 3. Equipment is manufactured at th Fig, 8147 rk given in the following through the transport network 16 a wi Fig. 847 ry x, can make ‘Ao units, factory m Units, depot y, needs 25 units ial depot ys on be transported to the ree factories %, % and x, and Is to be shipped to three depots yy, yy and yy ‘can make 20 units and factory x, can make 10 units. Depot yy needs 15 needs 10 units. How many Units should each factory make so that they TRees DISCRETE MATHEMATICS (358) jource sand a sink 2 28 shown in Free eien cave 8 avon rato eta aeacai tere Sora Rea aniaetie eaccriocapeetis of ne Devaatiores a Weer ee ee the edges (5, x) (s, x.) and (5, x). For the edges (yy, 2), (> 2) and (Ys 2) der a) labelling process to this network to find the value of maximum flow. i Fig, 8.148 4 Use labeling procedure to find a maximum flow inthe transport network shown in Fig. 8.149. Determine the corresponding minimum cut Fig. 8.149 POINTS TO REMEMBER “tree” isa simple connected graph without any circuits, ‘The eccentricity Ev) of a vertex vin a graph G is the distance fr ‘OM v to the vertex farthest from vin G. ie EW = mad Wiw) A forest isa set of disjoint tees ‘A rooted tree in which every nttior node has ayes ore esl bo mesh dee bo tetnahscrisert, vertices (leaves). Then, Wor the binary tee i given by ‘atmost m sons is called an me the weight Wo = Ft where's the length ofthe path ofthe lat | from the root of ‘he tee The full binay tee is called an optimal tree if ts weight is minimum, Let G be any connected graph. A spanning subgraph of @ PIGS 8 tTeelelcalled a sparring tree of G, le. SYPGTOPH OG, which sa tee and contains al the vertices 's called a spanning tree of G 006 le Orie i

You might also like