21ODMCT614-Discrete Mathematical Structure

Graphs 143 Example 2: Determine whether the given graph has an Euler circuit. Construct such a circuit when one exists. If no Euler circuit exists, determine whether the graph has an Euler path and construct such a path if one exists. By theorem 1, this graph does not have an Euler circuit because we have two vertices with odd degrees (a and d). This graph does have an Euler path by Theorem 2. The path is as follows: a, e, c, e, b, e, d, b, a, c, d. Example 3: Determine whether the given graph has an Euler circuit. Construct such a circuit when one exists. If no Euler circuit exists, determine whether the graph has an Euler path and construct such a path if one exists. By theorem 1, there is an Euler circuit because every vertex has an even degree. The circuit is as follows: a, b, c, d, e, f, g, h, i, a, h, b, i, c, e, h, d, g, c, a Example 4: Determine whether the given graph has an Euler circuit. Construct such a circuit when one exists. If no Euler circuit exists, determine whether the graph has an Euler path and construct such a path if one exists. CU IDOL SELF LEARNING MATERIAL (SLM)

144 Discrete Mathematical Structures There is no Euler circuit because b has a different out-degree and in-degree. There is also no Euler path because b’s in-degree and out-degree differ by more than 1. Example 5: Determine whether the given graph has an Euler circuit. Construct such a circuit when one exists. If no Euler circuit exists, determine whether the graph has an Euler path and construct such a path if one exists. There is no Euler circuit because there are vertices that do not have the same in-degree and out-degree. We also do not have a Euler path because we have more than two vertices whose in- degree and out-degree that differ by 1. Hamiltonian Graphs If there exists a closed walk in the connected graph that visits every vertex of the graph exactly once (except starting vertex) without repeating the edges,then such a graph is called as a Hamiltonian graph. Any connected graph that contains a Hamiltonian circuit is called as a Hamiltonian Graph. CU IDOL SELF LEARNING MATERIAL (SLM)

Graphs 145 Hamiltonian Graph Example- The following graph is an example of a Hamiltonian graph- Here,
This graph contains a closed walk ABCDEFA.
It visits every vertex of the graph exactly once except starting vertex.
The edges are not repeated during the walk.
Therefore, it is a Hamiltonian graph. Alternatively, there exists a Hamiltonian circuit ABCDEFA in the above graph, therefore it is a Hamiltonian graph. Hamiltonian Path A connected graph is said to be Hamiltonian if it contains each vertex of G exactly once. Such a path is called a Hamiltonian path. Example a b b c de Hamiltonian Path − e-d-b-a-c. CU IDOL SELF LEARNING MATERIAL (SLM)

146 Discrete Mathematical Structures Hamiltonian Path: A Hamiltonian circuit in a graph G is a circuit that includes every vertex (except first/last vertex) of G exactly once. e2 e1 v2 e3 v1 e4 v3 v1e1v2e3v3e4v1 is a Hamiltonian circuit. Example 6: Determine whether the given graph has an Hamilton circuit. If it does, find such a circuit. It it does not, give an argument to show why no such circuit exists. This graph has a Hamilton circuit. a, b, c, d, e, a is a circuit. Example 7: Determine whether the given graph has an Hamilton circuit. If it does, find such a circuit. It it does not, give an argument to show why no such circuit exists. There is no Hamilton circuit because there are vertices of degree 1 (pendants) in the graph. CU IDOL SELF LEARNING MATERIAL (SLM)

Graphs 147 Example 8: Determine whether the given graph has an Hamilton path. If it does, find such a path. It it does not, give an argument to show why no such path exists. There is a Hamilton path, one such path is: f, e, d, a, b, c. 8.6 Graph Coloring Graph coloring is the procedure of assignment of colors to each vertex of a graph G such that no adjacent vertices get same color. The objective is to minimize the number of colors while coloring a graph. The smallest number of colors required to color a graph G is called its chromatic number of that graph. Graph coloring problem is a NP Complete problem. Method to Color a Graph The steps required to color a graph G with n number of vertices are as follows − Step 1 − Arrange the vertices of the graph in some order. Step 2 − Choose the first vertex and color it with the first color. Step 3 − Choose the next vertex and color it with the lowest numbered color that has not been colored on any vertices adjacent to it. If all the adjacent vertices are colored with this color, assign a new color to it. Repeat this step until all the vertices are colored. CU IDOL SELF LEARNING MATERIAL (SLM)

148 Discrete Mathematical Structures Example: In the above figure, at first vertex a is colored red. As the adjacent vertices of vertex a are again adjacent, vertex b and vertex dd are colored with different color, green and blue respectively. Then vertex c is colored as red as no adjacent vertex of c is colored red. Hence, we could color the graph by 3 colors. Hence, the chromatic number of the graph is 3. Applications of Graph Coloring: Some applications of graph coloring include −
Register Allocation
Map Coloring
Bipartite Graph Checking
Mobile Radio Frequency Assignment
Making time table, etc. 8.7 Chromatic Number of a Graph The chromatic number of a graph is the minimum number of colors needed to produce a proper coloring of a graph. In our scheduling example, the chromatic number of the graph would be the minimum number of time slots needed to schedule the meetings, so there are no time conflicts. This scheduling example is a simple example, so we can find the chromatic number of the graph just using inspection. If we start by coloring vertex A with the color red, then we can see CU IDOL SELF LEARNING MATERIAL (SLM)

Graphs 149 that vertices B and C must be a different color than this since they share an edge with A. Furthermore, B and C also share an edge, so they have to be different colors as well, say blue and green. The only vertex left is D, and we see that it shares an edge with both B and C, so it can't be blue or green, but it does not share an edge with A, so it can be red. Meeting Meeting A B Meeting Meeting C D We can’t use less than 3 colors without two vertices sharing an edge having the same color. Therefore, the chromatic number of the graph is 3, and Sherry should schedule meetings during 3 time slots. With a little logic, that’s pretty easy! However, it can become quite difficult to find the chromatic number in more involved graphs. There are a number of algorithms for finding the chromatic number of a graph, and each of them would require their own lesson to explain. In this lesson, we will stick to simple graphs, where we can find the chromatic number with a little logic and inspection. CU IDOL SELF LEARNING MATERIAL (SLM)

150 Discrete Mathematical Structures Example 9: Find chromatic number of the following graph– Solution: Applying Greedy Algorithm, we have– Vertex a b c d e f C2 Color C1 C2 C1 C2 C1 From here,
Minimum number of colors used to color the given graph are 2.
Therefore, Chromatic Number of the given graph = 2. Example 10: Find chromatic number of the following graph– Solution: Applying Greedy Algorithm, we have– Vertex a b c d e f C1 Color C1 C2 C2 C3 C3 CU IDOL SELF LEARNING MATERIAL (SLM)

Graphs 151 From here,
Minimum number of colors used to color the given graph are 3.
Therefore, Chromatic Number of the given graph = 3. The given graph may be properly colored using 3 colors as shown below: 8.8 Summary One reason graph theory is such a rich area of study is that it deals with such a fundamental concept: any pair of objects can either be related or not related. What the objects are and what “related” means varies on context, and this leads to many applications of graph theory to science and other areas of math. The objects can be countries, and two countries can be related if they share a border. The objects could be land masses which are related if there is a bridge between them. The objects could be websites which are related if there is a link from one to the other. Or we can be completely abstract: the objects are vertices which are related if their is an edge between them. 8.9 Key Words/Abbreviations
Adjacency: The state of being adjacent; contiguity.
Graph: Collection of vertices and edges where each edge is assigned to a pair of vertices.
Bipartite: Divided into or consisting of two parts.
Chromatic Number: Smallest number of colors needed to color the vertices of Graph. CU IDOL SELF LEARNING MATERIAL (SLM)

152 Discrete Mathematical Structures
Graph Coloring: An assignment of colors to the vertices of the graph, so that no two adjacent vertices have the same color.
Indegree: number of edges which are coming into the vertex.
Outdegree: number of edges which are going out from the vertex.
Euler Path: A simple path containing every edge of G.
Euler Circuit: A simple circuit containing every edge of G.
Hamilton Circuit: A simple circuit that traverses every vertex in G exactly once.
Hamilton Path: A simple path that traverses every vertex in G exactly once. 8.10 Learning Activity 1. State difference between Path and Cycle in graph theory. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 2. Define Proper Subset with suitable example. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 3. What is Cyclic Graph and Acyclic Graph? Give Suitable example. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 4. State the type of Graph if all its vertices have the same degree. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- CU IDOL SELF LEARNING MATERIAL (SLM)

Graphs 153 8.11 Unit End Questions (MCQ and Descriptive) A. Descriptive Types Questions 1. How many edges are there in a graph with 8 vertices each of degree 4? 2. How many simple non-isomorphic graphs are possible with 3 vertices? 3. Let ‘G’ be a connected planar graph with 20 vertices and the degree of each vertex is 3. Find the number of regions in the graph. 4. Find chromatic number of the following graph: 5. Find the adjacency matrix A(G) of the following graph. B. Multiple Choice/Objective Type Questions 1. What is the number of edges present in a complete graph having n vertices. (a) n(n  1) (b) n(n 1) 2 2 (c) n (d) None of these 2. In a simple graph, the number of edges is equal to __________ times the sum of the degrees of the vertices. (a) two (b) three (c) one (d) four CU IDOL SELF LEARNING MATERIAL (SLM)

154 Discrete Mathematical Structures 3. Which of the following statements for a simple graph is correct? (a) Every path is a trail (b) Every trail is a path (c) Every trail is a path as well as every path is a trail (d) None of these 4. What is the maximum number of edges in a bipartite graph having 10 vertices? (a) 24 (b) 21 (c) 25 (d) 16 5. Which of the following is true? (a) A graph may contain no edges and many vertices (b) A graph may contain many edges and no vertices (c) A graph may contain no edges and no vertices (d) None of these Answers 1. (b), 2. (a), 3. (a), 4. (c), 5. (a) 8.12 References References Books: 1. http://discrete.openmathbooks.org/pdfs/dmoi-tablet.pdf 2. https://open.umn.edu/opentextbooks/textbooks/discrete-mathematics-an-open-introduction Web Resources: 1. https://www.geeksforgeeks.org/mathematics-graph-theory-basics/ 2. https://www.geeksforgeeks.org/mathematics-euler-hamiltonian-paths/ 3. https://www.gatevidyalay.com/graph-coloring-algorithm-how-to-find-chromatic-number/ CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 9 TREE Structure: 9.0 Learning Objectives 9.1 Introduction 9.2 Trees 9.3 Types of Tree 9.3.1 Rooted Tree 9.3.2 Ordered Rooted Tree 9.3.3 Binary Trees 9.3.4 Binary Expression Trees 9.3.5 Complete Binary Tree 9.4 Properties of Trees 9.5 Binary Search Tree 9.5.1 Algorithms for Searching and Inserting in a Binary Search Trees 9.5.2 Algorithms for Deleting in a Binary Search Trees 9.6 Tree Traversing (Preorder, Inorder and Post-order) 9.7 Summary of the Unit 9.8 Key Words/Abbreviations 9.9 Learning Activity

156 Discrete Mathematical Structures 9.10 Unit End Questions (MCQ and Descriptive) 9.11 References 9.0 Learning Objectives After studying this unit, you will be able to:
Define tree.
Describe different types of tree.
Discuss various properties of trees. 9.1 Introduction
Tree is a discrete structure that represents hierarchical relationships between individual elements or nodes. A tree in which a parent has no more than two children is called a binary tree.
A tree is a collection of nodes (dots) called a graph with connecting edges (lines) between the nodes. All nodes are connected by lines. An equivalent condition for T to be a tree: If v, w are nodes of T then there is a unique simple path from v to w.
A rooted tree R is a tree with a vertex designated as special, a “root.” These trees are usually drawn with their roots at the top and in such a way that the distance between the root an vertex v designates the level of the vertex v and is vertically aligned on its level. The height of a rooted tree is the eccentricity of the root. 9.2 Trees Definition An acyclic undirected graph that is connected is known as a Tree. For a tree with n number of vertices, the number of edges is (n – 1). CU IDOL SELF LEARNING MATERIAL (SLM)

Tree 157 Fig. 9.1 A graph is a tree if and only if there is exactly one path between every pair of its vertices. Fig. 9.2 The above graph is connected but contains cycle hence not tree. 9.3 Types of Tree There are different types of trees: 9.3.1 Rooted Tree A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root. Root The starting note of tree called as root. The root is a vertex with in degree 0. Leaf A vertex of a tree is called a leaf if it has no children, i.e., a vertex with out degree 0. Internal Vertices The vertices that have children as well as parent called interval vertices. CU IDOL SELF LEARNING MATERIAL (SLM)

158 Discrete Mathematical Structures Forest Collection of multiple trees together called forest. Level The level of a vertex V in a rooted tree is the length of the unique path from the root to this vertex. 9.3.2 Ordered Rooted Tree An Ordered rooted tree is a rooted tree where the children of each internal vertex are ordered. a b cd pqe f g no hi jk lm r Fig. 9.3 CU IDOL SELF LEARNING MATERIAL (SLM)

Tree 159 Example: a bc d e f gh i jk l mn op qr st u Fig. 9.4 Answer the following questions: 1. Which vertex is a root? Ans: A is the root of the tree. 2. Which vertices are internal? Ans: The internal vertices are b, c, d, f, h, j, q and t. 3. Which vertices are leave? Ans: The leaves are: e, g, i, k, l, m, n, o, p, r, s and u. 4. Which vertices are children of j? Ans: The children of j are q and r. 5. Which vertex is the parent of h? Ans: The parent of h is c. CU IDOL SELF LEARNING MATERIAL (SLM)

160 Discrete Mathematical Structures 6. Which vertices are siblings of o? Ans: The sibling of o is P. 9.3.3 Binary Trees Definition If the out degree of every node is less than or equal to 2, in a directed tree then the tree is called a binary tree. A tree consisting of the nodes (empty tree) is also a binary tree. A BC F DE G HI J K LM NO Fig. 9.5 Left Subtree The subtree whose root is the left child of some node is called the left subtree of that node. Right Subtree The subtree whose root is the right child of some node is called the right subtree of that node. Level of a Node The level of a node is it’s distance from the root. The level of root is defined as zero level of all other nodes is one more than it’s parent note. CU IDOL SELF LEARNING MATERIAL (SLM)

Tree 161 Depth or Height of a Tree The depth or height of a tree is defined as the maximum number of nodes in a branch of a tree. The depth of root is one. External Nodes The nodes which have no children are called external nodes or terminal nodes. 9.3.4 Binary Expression Trees The expression tree is a binary tree whose root contains the operator and whose left subtree contains the left expression and right subtree contains the right expression. Example: Construct the binary expression tree for the expression (a + b)* (d/c) Solution: The binary expression tree for the expression (a + b)* (b/c) is: * + / a bc d Fig. 9.6 9.3.5 Complete Binary Tree Complete binary tree is a binary tree if it is all levels, except possibly the last have the maximum number of possible nodes as far left as possible. The depth of the complete binary tree having n nodes is log2 n + 1. CU IDOL SELF LEARNING MATERIAL (SLM)

162 Discrete Mathematical Structures Example: The tree shown in figure is a complete binary tree. 1 2 3 4 56 7 89 Fig. 9.7 9.3.6 Full Binary Tree Full binary tree is a binary tree in which all the leaves are on the same level and every non- leaf node has two children. A BC D EF G Fig. 9.8 Difference between General Tree and Binary Tree General Tree Binary Tree 1. There is no such tree having zero nodes or an 1 There may be an empty binary tree empty general tree 2. If some nodes has a child, then there is no such 2. If some node has a child, then it is distinction distinguished as a left child or right child CU IDOL SELF LEARNING MATERIAL (SLM)

Tree 163 9.4 Properties of Trees 1. Every tree with at least two vertices has at least two leaves. 2. (a) Every edge of a tree is a cut-edge. (b) Adding one edge to a tree forms exactly one cycle. (c) Every connected graph contains a spanning tree. 3. Every tree contains at least one pandent vertex. 4. In tree there is a unique path between each pair of vertices. 9.5 Binary Search Tree Binary search trees have the property that the node to the left contains a smaller value than the node pointing to it and the node to the right contains a larger value than the node pointing to it. It is not necessary that a node in a ‘Binary Search Tree’ point to the nodes whose value immediately precede and follow it. Example: 8 7 14 5 9 20 26 Fig. 9.9 CU IDOL SELF LEARNING MATERIAL (SLM)

164 Discrete Mathematical Structures 9.5.1 Algorithms for Searching and Inserting in a Binary Search Trees Inserting into a Binary Search Tree Consider a binary tree T. Suppose, we have given an ITEM of information to insert in T. The ITEM is inserted as a leaf in the tree. The following steps explain a procedure to insert on ITEM in the binary search tree T. Algorithm
Step 1: Compare the ITEM with the root node.
Step 2: If ITEM > ROOT NODE, proceed to the right child and it becomes a root node for the right subtree.
Step 3: If ITEM < ROOT NODE, proceed to the left child.
Step 4: Repeat the above steps until, we meet a node which has no left and right subtree.
Step 5: Now if the ITEM is greater than the node, then the ITEM is inserted as the right child and if the ITEM is less than the node then the ITEM is inserted as the left child. Example: Show the binary search tree after inserting 3, 1, 4, 6, 9, 2, 5, 7 into an initially empty binary search tree. Solution: The insertion of the above nodes in the empty binary search tree is: Insert 3 3 Insert 1 3 1 CU IDOL SELF LEARNING MATERIAL (SLM)

Tree 165 Insert 4 Insert 6 3 Insert 9 1 4 3 1 4 3 6 4 1 6 9 CU IDOL SELF LEARNING MATERIAL (SLM)

166 Discrete Mathematical Structures Insert 2 3 Insert 5 1 4 2 6 9 3 1 4 2 6 59 CU IDOL SELF LEARNING MATERIAL (SLM)

Tree 167 Insert 7 3 1 4 2 6 59 7 Searching an Element in Binary Search Tree To search a given element in binary search tree, we first compare it with root. If the element is present at root, we return root. If element is greater than root, we recur for right subtree of root node. Otherwise, we recur for left subtree. Algorithm
Step 1: Start from root. Compare element with root.
Step 2: If the element is less than root, then recurse for left. Else recourse for right.
Step 3: If element to search is found anywhere, return true. Else return false. CU IDOL SELF LEARNING MATERIAL (SLM)

168 Discrete Mathematical Structures Example: Search element 6 in below tree. 8 3 10 16 14 4 7 13 Fig. 9.10 Solution: Start with root. 8 Since 6 is less than 8 move to left subtree 8 3 CU IDOL SELF LEARNING MATERIAL (SLM)

Tree 169 Left child at 8 is 3, 6 is greater than 3 move to right to subtree. 8 3 8 The right child of 3 is 6. Hence, element found. 9.5.2 Algorithms for Deleting in a Binary Search Trees Consider a binary search tree T. Suppose, we want to delete a given ITEM from binary search tree. To delete an ITEM from a binary search tree, we have three cases, depending upon the number of children of the deleted node:
Case (1): Deleted node has no children: Deleting a node which has no children is very simple, as replace the node with null.
Case (2): Deleted node has only one child: Replace the value of a deleted node with the only child.
Case (3): Deleted node has only two children: In this case, replace the deleted node with the node that is closest in the value to the deleted node. To find the nearest value, we move once to the left and then to the right as far as possible. This node is called the immediate predecessor. Now, replace the value of the deleted node with the immediate predecessor and then delete the replaced node by using Case 1 or Case 2. CU IDOL SELF LEARNING MATERIAL (SLM)

170 Discrete Mathematical Structures Example: Delete the root node of the following tree. 3 1 4 2 6 59 7 Fig. 9.11 Solution: To delete the root node, first replace the root node with the closest elements of the root. For this, first, move one step left and then to the right as far as possible to the node. Then delete the replaced node. The tree after deletion is: CU IDOL SELF LEARNING MATERIAL (SLM)

Tree 171 2 4 1 6 9 5 7 Fig. 9.12 9.6 Tree Traversing (Preorder, Inorder and Post-order) Traversing means to visit all the nodes of the tree. There are three standard methods to traverse the binary trees. These are as follows: 1. Preorder Traversal 2. Postorder Traversal 3. Inorder Traversal 1. Preorder Traversal The preorder traversal of a binary tree is a recursive process. The preorder traversal of a tree is:
Visit the root of the tree.
Traverse the left subtree in preorder.
Traverse the right subtree in preorder. CU IDOL SELF LEARNING MATERIAL (SLM)

172 Discrete Mathematical Structures 2. Postorder Traversal The postorder traverse of a binary tree is a recursive process. the postorder traversal of a tree is:
Traverse the left subtree in postorder.
Traverse the right subtree in postorder.
Visit the root of the tree. 3. Inorder Traversal The inorder traversal of a binary tree is a recursive process the inorder traversal of a tree is:
Traverse in inorder the left subtree.
Visit the root of the tree.
Traverse in inorder the right subtree. Example: Determine the preorder, postorder and inorder traversal of the binary tree as shown below. A BC F DE G HI J K LM N O Fig. 9.13 CU IDOL SELF LEARNING MATERIAL (SLM)

Tree 173
Preorder: ABDGHEIJLM
Postorder: GHDILMJEBNOKFCA
Inorder: GDHBIELJMACFNKO 9.7 Summary
A tree is a mathematical structure that can be viewed as either a graph or as a data structure. The two views are equivalent, since a tree data structure contains not only a set of elements, but also connections between elements, giving a tree graph.
A tree is a set of straight line segments connected at their ends containing no closed loops (cycles). In other words, it is a simple, undirected, connected, acyclic graph (or, equivalently, a connected forest). A tree with n nodes has n – 1 graphedges. Conversely, a connected graph with n nodes and n – 1 edges is a tree. All trees are bipartite graphs. Trees with no particular node singled out are sometimes called freetrees by way of distinguishing them from rooted trees.
The points of connection are known as forks and the segments as branches. Final segments and the nodes at their ends are called tree leaves. A tree with two branches at each fork and with one or two tree leaves at the end of each branch is called a binary tree.
Tree Traversal Procedures for systematically visiting every vertex of an ordered tree are called traversals. The three most commonly used traversals are preorder traversal, inorder traversal, and postorder traversal.
Depth-First Search to use depth-first search to build a spanning tree for a connected simple graph first arbitrarily choose a vertex of the graph as the root. Form a path starting at this vertex by successively adding vertices and edges, where each new edge is incident with the last vertex in the path and a vertex not already in the path. CU IDOL SELF LEARNING MATERIAL (SLM)

174 Discrete Mathematical Structures 9.8 Key Words/Abbreviations
Trees: The hierarchical relationships between the individual elements.
Rooted Tree: A tree in which one vertex has been designated the root.
Forest: An undirected graph in which any two vertices are connected by at most one path.
Siblings: Vertices with the same parent.
Leaf: A vertex of a tree, if it has no children.
Internal Vertices: Vertices that have children.
Height: The length of the longest path from the root to any vertex.
Ordered rooted tree: A rooted tree where the children of each internal vertex are ordered. 9.9 Learning Activity 1. Draw the different trees on vertice T4. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 2. Explain the Isomorphism’s of Tree. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 3. What is Spanning tree? ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- CU IDOL SELF LEARNING MATERIAL (SLM)

Tree 175 9.10 Unit End Questions (MCQ and Descriptive) A. Descriptive Types Questions 1. Detemine the preorder, postorder and inorder traversal of the binary tree. 1 26 3 47 8 5 9 11 10 2. What is the prefix form for the expression [(a + b)c] + 7 3. Find the final tree T. If the following numbers are inserted into an empty binary search tree T: 25, 38, 95, 18, 27, 11, 48, 55, 16 4. Search element 8 in the following the binary search tree, also insert element 14. 24 19 27 12 21 25 44 CU IDOL SELF LEARNING MATERIAL (SLM)

176 Discrete Mathematical Structures 5. Given a tree T is a binary tree stored in the memory as in the following figure. 1 Info Left Right 2 E 58 3 B 41 4 C 86 5 D 00 6 G 00 7 F 00 8 H 00 A 23 (a) Draw the tree T (b) Traverse T in: (i) Inorder (ii) Preorder (iii) Postorder Answers: 1. Preorder 1 2 3 4 5 6 7 8 9 10 11 Postorder 3 5 4 2 7 10 9 11 8 6 1 Inorder 3 2 5 4 1 7 6 9 10 8 11 B. Multiple Choice/Objective Type Questions 1. The number of edges from the root to the node is called ________ of the tree. (a) Height (b) Depth (c) Length (d) None of these CU IDOL SELF LEARNING MATERIAL (SLM)

Tree 177 2. The number of edges from the node to the deepest leaf is called ________ of the tree. (a) Height (b) Depth (c) Length (d) None of these 3. What is a full binary tree? (a) Each node has exactly zero or two children. (b) Each node has exactly two children (c) All the leaves are at the same level. (d) Each node has exactly one or two children. 4. An acyclic undirected graph that is connected is known as a ________. (a) Graph (b) Digraph (c) Tree (d) Rooted tree 5. The starting note of tree called as ________. (a) Vertex (b) node (c) source point (d) root Answers 1. (b), 2. (a), 3. (a), 4. (c), 5. (d) 9.11 References References Book: 1. https://web.itu.edu.tr/~gencata/courses/DM/trees.pdf Web Resources: 1. http://staff.scem.uws.edu.au/cgi-bin/cgiwrap/zhuhan/dmath/dm_readall.cgi?page=16 2. https://www.javatpoint.com/discrete-mathematics-introduction-of-trees 3. http://mathworld.wolfram.com/Tree.html 4. http://mathworld.wolfram.com/RootedTree.html CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 10 BOOLEAN ALGEBRA Structure: 10.0 Learning Objectives 10.1 Introduction 10.2 Boolean Algebra 10.2.1 Definition 10.2.2 Boollean Operations 10.1.3 Truth Tables for the Laws of Boolean 10.2.4 Boolean Algebra Functions 10.3 Languages Recognition and Generation 10.3.1 Languages and Grammars 10.3.2 Regular Expression 10.3.3 Regular Languages 10.4 Phase Structure Grammars and Languages (Finite) 10.4.1 Phrase Structure Grammars 10.4.2 Finite-State Automata 10.5 Summary of the Unit 10.6 Key Words/Abbreviations 10.7 Learning Activity

Boolean Algebra 179 10.8 Unit End Questions (MCQ and Descriptive) 10.9 References 10.0 Learning Objectives After studying this unit, you will be able to:
Explain various Boolean Operations.
Explain Laws of Boolean Operations.
Describe Various Boolean Techniques. 10.1 Introduction
Boolean algebra is a logical algebra in which symbols are used to represent logic levels. Any symbol can be used, however, letters of the alphabet are generally used. Since, the logic levels are generally associated with the symbols 1 and 0, whatever letters are used as variables that can take the values of 1 or 0.
Logic sentences that can be expressed in classical propositional calculus have an equivalent expression in Boolean algebra. Thus, Boolean logic is sometimes used to denote propositional calculus performed in this way. Boolean algebra is not sufficient to capture logic formulas using quantifiers, like those from first order logic. 10.2 Boolean Algebra 10.2.1 Definition Boolean Algebra uses a set of Laws and Rules to define the operation of a digital logic circuit. As well as the logic symbols “0” and “1” being used to represent a digital input or output, we can also use them as constants for a permanently “Open” or “Closed” circuit or contact respectively. Boolean algebra or switching algebra is a system of mathematical logic to perform different mathematical operations in binary system. These are only two elements 1 and 0 by CU IDOL SELF LEARNING MATERIAL (SLM)

180 Discrete Mathematical Structures which all the mathematical operations are to be performed. There only three basis binary operations, AND, OR and NOT by which all simple as well as complex binary mathematical operations are to be done. There are many rules in Boolean algebra by which those mathematical operations are done. In Boolean algebra, the variables are represented by English Capital Letter like A, B, C etc and the value of each variable can be either 1 or 0, nothing else. 10.2.2 Boollean Operations Boolean algebra has only two mathematical operations, addition and multiplication. These operations are associated with the OR gate and the AND gate, respectively. 1. Logical Addition When the + (the logical addition) symbol is placed between two variables, say X and Y, since, both X and Y can take only the role 0 and 1, we can define the + Symbol by listing, all possible combinations for X and Y and the resulting value of X + Y. The possible input and output combinations may arranged as follows: 0+0=0 0 + 1 =1 1+0 =1 1+1 =1 This table represents a standard binary addition, except for the last entry. When both' X and Y represents 1’s, the value of X + Y is 1. The symbol + therefore does not has the “Normal” meaning, but is a Logical addition symbol. The plus symbol (+) read as “OR”, therefore, X +Y is read as X or Y. This concept may be extended to any number of variables, for example, A + B + C + D = E Even if A, B, C and D all had the values 1, the sum of the values, i.e., is 1. CU IDOL SELF LEARNING MATERIAL (SLM)

Boolean Algebra 181 2. Logical Multiplication We can define the “.” (logical multiplication) symbol or AND operator by listing all possible combinations for (input) variables X and Y and the resulting (output) value of X. Y as, 0.0=0 0.1=0 1.0=0 1.1=1 10.1.3 Truth Tables for the Laws of Boolean Boolean Description Equivalent Switching Boolean Algebra Law Expression Circuit or Rule A+1=1 A in parallel with closed = Annulment “CLOSED” A+0=A A in parallel with open = “A” Identity A.1=A A in series with closed = “A” Identity A.0=0 A in series with open = “OPEN” Annulment Idempotent A+A=A A in parallel with A = “A” A.A=A A in series with A = “A” Idempotent Double Negation NOT A = A NOT NOT A (double negative) Complement A+A=1 = “A” A in parallel with NOT A = “CLOSED” CU IDOL SELF LEARNING MATERIAL (SLM)

182 Discrete Mathematical Structures Complement A.A=0 A in series with NOT A = Commutative “OPEN” A + B = B + A A in parallel with B = B in parallel with A A.B=B.A A in series with B = B in series Commutative with A A+B = A.B invert and replace OR with deMorgan’s Theorem A.B = A+B AND deMorgan’s Theorem invert and replace AND with OR 10.2.4 Boolean Algebra Functions Using the information above, simple 2-input AND, OR and NOT Gates can be represented by 16 possible functions as shown in the following table. Function Description Expression 1. NULL 0 2. IDENTITY 1 3. Input A A 4. Input B B 5. NOT A A 6. NOT B B 7. A AND B (AND) A.B 8. A AND NOT B A.B 9. NOT A AND B A.B NOT AND (NAND) A.B 10. A OR B (OR) A+B 11. A OR NOT B A+B 12. NOT A OR B A+B 13. CU IDOL SELF LEARNING MATERIAL (SLM)

Boolean Algebra 183 14. NOT OR (NOR) A+B 15. Exclusive-OR A.B+A.B 16. Exclusive-NOR A.B+A.B Example 1: Using Boolean laws, simplify the following expression: (A + B) (A + C). Solution: Q = (A + B).(A + C) A.A + A.C + A.B + B.C – Distributive law A + A.C + A.B + B.C – Idempotent AND law (A.A = A) A(1 + C) + A.B + B.C – Distributive law A.1 + A.B + B.C – Identity OR law (1 + C = 1) A(1 + B) + B.C – Distributive law A.1 + B.C – Identity OR law (1 + B = 1) Q = A + (B.C) – Identity AND law (A.1 = A) Then the expression: (A + B) (A + C) can be simplified to A + (B.C) as in the Distributive law. 10.3 Languages Recognition and Generation 10.3.1 Languages and Grammars Words in the English language can be combined in various ways. The grammar of English tells us whether a combination of words is a valid sentence. For instance, the frog writes neatly is a valid sentence, because it is formed from a noun phrase, the frog, made-up of the verb writes and the adverb neatly. We do not care that this is a nonsensical statement, because, we are concerned only with the syntax or form of the sentence, and not it’s semantics or meaning we also note that the combination of words swims quickly mathematics is not a valid sentence because, it does not follow the rules of English grammar. The syntax of a natural language, that is, a spoken language, such as English, French, German or Spanish, is extremely complicated. In fact, it does not seem possible to specify all the CU IDOL SELF LEARNING MATERIAL (SLM)

184 Discrete Mathematical Structures rules of syntax for a natural language. Research in the automatic translation of one language to another has led to the concept of a formal language, which, unlike a natural language, is specified by a well-defined set of rules of syntax. Rules of syntax are important not only in linguistics, the study of natural languages, but also in the study of programming languages. 10.3.2 Regular Expression Regular expressions are used to denote regular languages. An expression is regular if:

is a regular expression for regular language
.
 is a regular expression for regular language {}.
If a   ( represents the input alphabet) a regular expression with language {a}.
If a and b are regular expression, a + b is also a regular expression with language {a, b}.
If a and b are regular expression, ab (concatenation of a and b) is also a regular.
If a is regular expression, a* (0 or more times a) is also regular. 10.3.3 Regular Languages A language is regular if it can be expressed in terms of regular expression. Regular Expression Regular Language 1. Set of Vovels (a  e ,  o  u) {a, c, i, o u} 2. A followed by o or more b (a, b*) {a, ab, abb, abbb, abbbb ..} 3. Any number of vowels v*.c* (where v – values and c – {e, a, aou, aiou, b, abcd} where e followed by any number of consonants consonants) represent empty string (in case 0 vowels and 0 consonants) 10.4 Phase Structure Grammars and Languages (Finite) 10.4.1 Phrase Structure Grammars Definition 1 A vocabulary (or alphabet) V is a finite, non-empty set of elements called symbols. A word (or sentence) over V is a string of finite length of elements of V. The empty string or null string CU IDOL SELF LEARNING MATERIAL (SLM)

Boolean Algebra 185 denoted by  is the string containing no symbols. The set of all words over V is denoted by V*. A language over V is a subset of V*. Note that , the empty string, is the string containing no symbols. It is different from , the empty set. It follows that [] is the set containing exactly one string, namely, the empty string. Definition 2 A phrase structure grammar G = {V, T, S, P} consists of a vocabulary V, a subset T of V consisting of terminal symbols, a start symbol S from V, and a finite set of productions P. The set V – T is denoted by N. Elements of N are called non-terminal symbols. Every production in p must contain at least one non-terminal on its left side. Example 2: Let G = {V, T, S, P} where v = {a, b, A, B, S} T = {a, b}, S is the start symbol and P = {S  ABa, A  BB, B  ab, AB  b} G is an example of a phrase structure grammar. We will be interested in the words that can be generated by the productions of a phrase structure grammar. Definition 3 Let G = {V, T, S, P} be a phrase structure grammar, let w0 = lZ0r (i.e., the concatination of l, Z0 and r) and w1 = lZ, r be strings over V. If Z0  Z1 is a production of G, we say that w1 is directly derivable from w0 and we write w0  w1. If w0, w1, w2,....,wn are from w0 and we write w0, w1, w2, ..., wn are from w0 and we write w0*  wn. The sequence of steps used to obtain wn from w0 is called a derivation. Example 3: The string Aaba is directly derivable from ABa in the grammar in Example 1 because B ab is a production in the grammar. The string abababa is derivable from ABa because ABa  Aaba  BBaba  Bababa  abababa, using the productions B  ab, A  BB, B  ab and B  ab in succession. CU IDOL SELF LEARNING MATERIAL (SLM)

186 Discrete Mathematical Structures Definition 4 Let G = {V, T, S, P) be a phrase structure grammar. The language generated by G (or the language of G), denoted by L(G), is the set of all strings of terminals that are derivable from the starting state S. In other words, L(G) = {wT*/S*  w} In Example 3 and Example 4, we find the language generated by a phrase structure grammar. Example 4: Let G be the grammar with vocabulary. V = {S, A, a, b}, set of terminals T = {a, b}, starting symbol S, and productions. p = {S  aA, S  b, A  aa} what is L(G) the language of the grammar? Solution: From the start state S, we can derive aA using the production S  aA. we can also use the production S  b to derive b, from aA production A  aa can be used to derive aaa. No additional words can be derived. Hence, L(G) = {b, aaa}. Example 5: One grammar that generates the set {0n 1n 2n/n = 0, 1, 2, 3} is G = {V, T, S, P} with V = {0,1, 2, S, A, B, C}; T = {0, 1, 2}. Starting state S: and productions S  C, C  OCAB, S  , BA  AB, OA  O1, 1A  11, 1B  12, and 2B  22. 10.4.2 Finite-state Automata (Designing a Finite State Automata) We can construct a finite-state automation that recognizes a given sold strings by carefully adding states and transitions and determining which of these states should be final states. When appropriate, we include states that can keep track of some of the properties of the input string, providing the finite state automaton with limited memory. CU IDOL SELF LEARNING MATERIAL (SLM)

Boolean Algebra 187 Example 6: Construct deterministic finite state, automata that recognize each of these languages: (i) The set of bit strings that begin with two 0’s. (ii) The set of bit strings that contain two consecutive 0’s. (iii) The set of bit strings that do not contain two consecutive 0’s. (iv) The set of bit strings that and with two 0’s. (v) The set of bit strings that contain at least two 0’s. Solution: (i) Our goal is to construct a deterministic finite-state automaton that recognizes the set of bit strings that begin with two 0’s. Besides the start state S0, we include a non-final state S1: we move to S1 from S0 if the first bit is a 0. Next, we add a final state S2, which we move to from S1 if the second a bit is a.0. When we have reached S2, we know that the first two input bits are both 0s, so, we stay in the state S2 no matter what the succeeding bits (if any) are. We move to a non-final state S3 from S0 if the first bit is a 1 and from S1 if the second bit is a 1. 0, 1 Fig. 10.1 (ii) Our goal is to construct a deterministic finite-state automation that recognizes the set of bit strings that contains two consecutive 0s. Besides the start state S0, we include a non- CU IDOL SELF LEARNING MATERIAL (SLM)

188 Discrete Mathematical Structures final state S1 which tells us that the last input bit seen is a 0, but either the bit before it was a 1, or the bit was the initial bit of the string. We include a final state S2 that we move to from S1 when the next input bit after a 0 is also a 0. If a 1 follows a 0 in the string (before we encounter two consecutive 0s) we return to S0 and begin looking for consecutive 0s all over again. 0, 1 Fig. 10.2 (iii) Our goal is to construct a deterministic finite-state automaton that recognizes the set of bit strings that do not contain two consecutive 0’s. Besides the start state S0 which should be a final state, we include a final state S1 which we move to from S0 when 0 is the first input bit. When an input bit is a1, we return to, or stay in, state S0. We add a state S2, which we move to from S1 when the input bit is a 0. Reaching S2 tells us that we have been two consecutive 0s as input bits. We stay in state S2 once we have reached it. this state is not final. 0, 1 Fig. 10.3 (i) Our goal is to construct a deterministic finite-state automation that recognizes the set of bit strings that end with two 0s. Besides the start state S0, we include a non-final state S1 which we move to if the first bit is 0. We include a final state S2 which we move to from CU IDOL SELF LEARNING MATERIAL (SLM)

Boolean Algebra 189 S1 if the next input bit after a 0 is also a 0. If an input of 0 follows a previous 0, we stay in State S2 because the last two input bits are still 0s. Once we are in state S2, an input bit of 1 sends as back to S0, and we begin looking for consecutive 0s all over again. We also return to S0 if the next input is a 1 when we are in state S1. Fig. 10.4 (ii) Our goal is to construct a deterministic finite-state automation that recognizes the set of bit strings that contain two 0s. Besides the start state, we include a state. S1, which is not final; we stay in S0 until an input bit is a 0 and we move to S1 when we encounter the first 0 bit in the input. We add a final state S2, which we move to from S1 once we encounter a second 0 bit whenever we encounter a, 1 as input, we stay in the current state. Once we have reached S2, we remain there. Here S1 and S2 are used to tell us that we have already seen one or two 0’s in the input string So for, respectively. 0, 1 Fig. 10.5 CU IDOL SELF LEARNING MATERIAL (SLM)

190 Discrete Mathematical Structures 10.5 Summary of the Unit
Algebra of logic is known as Boolean algebra. The variables which can have two discrete values 0 (False) and 1 (True) and the operations of logical significance are dealt with Boolean algebra.
Boolean algebra is widely accepted in switching theory, building basic electronic circuits and designing of the digital computers. Boolean algebra has only two mathematical operations, addition and multiplication. These operations are associated with the OR gate and the AND gate, respectively.
The relationships are based on variables and constants:  The identifier for the AND logical operator is. (the dot).  The identifier for the OR logical operator is + (the mathematical addition symbol).  The identifier for the NOT logical operator is – (a bar across the expression).  The identifier for the EX-OR logical operator is Å (an encircled addition symbol).
A grammar defining formal language L is a quadruple (N, T, R, S), where N is a finite set of nonterminals, T is a finite set of terminal symbols, R is a finite set of productions, and S is an element of N.
The set of all strings that can be derived from a grammar is said to be the language generated from that grammar. A language generated by a grammar G is a subset formally defined by L(G) = {W | W *, S  G W} 10.6 Key Words/Abbreviations
Boolean algebra: A division of mathematics which deals with operations on logical values and incorporates binary variables. CU IDOL SELF LEARNING MATERIAL (SLM)

Boolean Algebra 191
Boolean Variables Value (Bit) Alternate Names 0 F, False, No, OFF, LOW 1 T, True, Yes, ON, HIGH
Boolean Operations Operator Name Alternate Name Example Alternate Representations NOT complement x x inversion OR x y, x  y, x & y logical addition union AND xy x  y, x y, x y intersection logical xy multiplication
Phrase structure grammar: A type of generative grammar in which constituent structures are represented by phrase structure rules or rewrite rules.
Regular expressions are used to denote regular languages.
is a regular expression for regular language
.  is a regular expression for regular language {}. If a  ( represents the input alphabet) a regular expression with language {a}. If a and b are regular expression, a + b is also a regular expression with language {a,b}. If a and b are regular expression, ab (concatenation of a and b) is also a regular. If a is regular expression, a* (0 or more times a) is also regular. CU IDOL SELF LEARNING MATERIAL (SLM)

192 Discrete Mathematical Structures 10.7 Learning Activity 1. Draw the Logic Symbol and Switch Symbol for each of following: (a) AND gate (b) OR gate (c) NOT gate ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 2. State the different Boolean Algebra Functions. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 10.8 Unit End Questions (MCQ and Descriptive) A. Descriptive Types Questions 1. Given Figure: x1 x3 x2 x2 Fig. 10.6 (a) Write the Boolean function that represents the given on-off circuit. (b) Show that the Boolean function obtained in answer to part a can be reduced to f Hx1, x2L = x1. Draw the on-off circuit diagram of this simplified representation. (c) Draw the circuit (gate) diagram of the given on-off circuit diagram. CU IDOL SELF LEARNING MATERIAL (SLM)