5-Discrete-Mathematics-munotes

Page 1

1Unit I
Recurrence Relations
1
FUNCTIONS
Unit Structure:
1.1 Introduction.
1.2 Functions.
1.3 Domain, Co -domain and the range of a function.
1.4 Injective, surjective and bijective functions.
1.5 Composite and inverse functions
1.5 Summary
1.6 Exercise
1.7 Reference.
1.1 INTRODUCTION
In many instances we assign to each element of a set a particular
element of a second set (which may be the same as the first). For example,
suppose that each student in a discrete mathematics class is assigned a
letter grade from the set {A, B, C, D, F}. And suppose that the grades are
Afor Adams, C for Chou, B for Good friend, A for Rodriguez, and F for
Stevens.
1.2 FUNCTIONS
Let A and B be nonempty sets. A function f from A to B is an
assignment of exactly one element of B to each element of A. We writ ef
(a) = b if b is the unique element of B assigned by the function f to the
element a of A. If f is a function from A to B, we write f : A →B.
Functions are sometimes also called mappings or transformations.
e.g. f(x) = x2shows us that function "f" ta kes "x" and squares it. Here f
stands for function; x stands for input; x2stands for output.
f(x) = x2munotes.in

Page 2

2Function Input Output
Input Relationship Output
0 x20
1 x21
2 x24
3 x29
4 x216
5 x225
… x2…
Functions are specified in many different ways. Sometimes we
explicitly state the assignments, as in Figure 1. Often we give a formula,
such as f (x) = x + 1, to define a function. Other times we use a computer
program to specify a function.
If f is a function from A to B, we say that A is the domain of f and
B is the codomain of f. If f (a) = b, we say that b is the image of a and a is
a preimage of b. The range, or image, of f is the se t of all images of
elements of A. Also, if f is a function from A to B, we say that f maps
At oB .
1.3 DOMAIN, CO -DOMAIN AND THE RANGE OF A
FUNCTION
Let G be the function that assigns a grade to a student in our
discrete mathematics class. Note that G(Adams) = A, for instance. The
domain of G is the set {Adams, Chou, Goodfriend, Rodriguez, Stevens},
and the codomain is the set {A, B, C, D, F}. The range of G is the set {A,
B, C, F}, because each grade except D is assigned to some student.
Generally function is called as domain. The Possible outcome is
called as co -domain. The actual outcome is called as range of a function.
Consider a function f(x) = 2x + 1
AB12
3
412
3
4
5
6
7
8
9munotes.in

Page 3

3In above example A = {1, 2, 3, 4 } is domain , B = {1,2,3,4,5,6,7,8,9 } is a
co-domain and Range = {3, 5, 7, 9}
Range is calculated in following manner:
f(x) = 2x + 1 …. For x =1 …… f(1) = 2 (1) + 1= 2 + 1 = 3
f(x) = 2x + 1 …. For x =2 …… f(1) = 2 (2) + 1= 4 + 1 = 5
f(x) = 2x + 1 …. For x =3 …… f(1) = 2 (3) + 1= 6 + 1 = 7
f(x) = 2x + 1 …. For x =4 …… f(1) = 2 (4) + 1= 8 + 1 = 9
1.4 INJECTIVE, SURJECTIVE AND BIJECTIVE
FUNCTIONS
Injective
A function f is injective if and only if whenever f(x) = f(y), x = y.
Exampl e: f(x) = x+5 from the set of real numbers real numbers to real
numbers is an injective function.
Is it true that whenever f(x) = f(y), x = y ?
Imagine x=3, then:
f(x) = 8
Now I say that f(y) = 8, what is the value of y? It can only be 3, so x=y
Surjectiv e
A function f (from set A to B) is surjective if and only if for every
y in B, there is at least one x in A such that f(x) = y, in other words f is
surjective if and only if f(A) = B.
In simple terms: every B has some A.
Example: The function f(x) = 2x from the set of natural numbers to the set
of non -negative even numbers is a surjective function.
BUT f(x) = 2x from the set of natural numbers to natural numbers is not
surjective, because, for example, no member in natura ln u m b e r sc a nb e
mapped to 3 by this function.
Bijective
A function f (from set A to B) is bijective if, for every y in B, there is
exactly one x in A such that f(x) = y
Alternatively, f is bijective if it is a one -to-one correspondence between
those set s, in other words both injective and surjective.
Example: The function f(x) = x2from the set of positive real numbers to
positive real numbers is both injective and surjective. Thus it is also
bijective.
But the same function from the set of all real numbers real
numbers is not bijective because we could have, for example, both
f(2)=4 andf( -2)=4munotes.in

Page 4

41.5 COMPOSITE AND INVERSE FUNCTIONS
The process of combining functions so that the output of one
function bec omes the input of another is known as a composition of
functions. The resulting function is known as a composite function. We
represent this combination by the following notation:
(f∘g)(x) =f(g(x))
We read the left -hand side as “ f“  composed with g  at x , and
the right -hand side as “ f  of g of x .” The two sides of the equation have
the same mathematical meaning and are equal. The open circle symbol, ∘
, is called the composition operator. Composition is a binary operation that
takes two funct ions and forms a new function, much as addition or
multiplication takes two numbers and gives a new number.
Iff(x)= −2xf(x)= −2xandg(x)=x2 −1g(x)=x2 −1,evaluate  f(g(3))f(g(3))  an
dg(f(3))g(f(3)) .
To evaluate f(g(3))f(g(3)) , first substitute, or input the value
of33intog(x)g(x) and find the output. Then substitute that value into
thef(x)f(x) function, and simplify:
g(3)=(3)2 −1=9−1=8g(3)=(3)2 −1=9−1=8,f(8)= −2(8)= −16f(8)= −2(8)= −16
Therefore, f(g(3))= −16
To evaluate g(f(3))g(f(3)) , find f(3)f(3) and t hen use that output value as
the input value into the g(x)g(x) function:
f(3)= −2(3)= −6f(3)= −2(3)= −6,g(−6)=(−6)2−1=36 −1=35g( −6)=(−6)2−1=3
6−1=35
Therefore, g(f(3))=35
An inverse function, which is notated f−1(x), is defined as the
inverse function of f(x)if it consistently reverses the f(x)process. That is,
iff(x)turns aaintobb, then f−1(x)must turn bintoa. More concisely and
formally, f−1(x)is the inverse function of f(x)if:
f(f−1(x))=x
Below is a mapping of function f(x) and its inverse functi on,f−1(x).
Notice that the ordered pairs are reversed from the original function to its
inverse. Because (x)maps ato3, the inverse f−1(x) maps 3back to a.
2.5 SUMMARY
This chapter gives introductory review on functions and their
examples. It will create base for advanced level.munotes.in

Page 5

52.6 EXERCISE
1. Specify a codomain for each. Under what conditions is each of these
functions withthe codomain you specified onto?
• A= { 1 , 2 , 3 , 4 }B={ a , b , c , d }
• f:A B is a function defined as
i.f(1) = b, f(2) = b, f(3) = b, f(4) =b
ii.f(1) = b, f(2) = c, f(3) = d, f(4) = a
iii.f(1) = a, f(2) = a, f(3) = b
iv.f(1) = b, f(1) = a, f(3) = b, f(4) =d
vf ( 1 )=b ,f ( 2 )=a ,f ( 3 )=b ,f ( 5 )= c
3. Give an example of a function from N to N that is
a) one -to-one but not onto.
b) onto but not one -to-one.
c) both onto and one -to-one (but different from the identity function).
d) neither one -to-one nor onto.
4. Give an explicit formula for a function from the set ofintege rs to the set
of positive integers that is
a) one -to-one, but not onto.
b) onto, but not one -to-one.
c) one -to-one and onto.
d) neither one -to-one nor onto
2.7 REFERENCES: -
1. Discrete Mathematics and Its Applications, Seventh Edition by Kenneth
H. Rosen, McGraw Hill Education (India) Private Limited. (2011)
2. Norman L. Biggs, Discrete Mathematics, Revised Edition, Clarendon
Press, Oxford 1989.
3. Data Structures Seymour Li pschutz, Schaum’s out lines, McGraw -Hill
Inc.
4. Elements of Discrete Mathematics: C.L. Liu , Tata McGraw -Hill
Edition .
5. Concrete Mathematics (Foundation for Computer Science): Graham,
Knuth, Patashnik Second Edition, Pearson Education.
6. Discrete Mathematics: Semyour Lipschutz, Marc Lipson, Schaum’s
out lines, McGraw -Hill Inc.
7. Foundations in Discrete Mathematics: K.D. Joshi, New Age
Publication, New Delhi.
munotes.in

Page 6

62
RELATIONS
Unit Structure: -
2.1 Introduction.
2.2 Definition and Examples
2.3 Properties of Relations
2.4 Partial Ordering Set.
2.5 Hasse Diagram.
2.6 Maximum and Minimum Element
2.7Summary
2.8 Exercise
2.9 Reference.
2.1 INTRODUCTION
A relation between two sets is a collection of ordered pairs
containing one object from each set. If the object x is from the first set and
the object y is from the second set, then the objects are said to be related if
the ordered pair (x,y) is in the rel ation. A function is a type of relation.
2.2 DEFINITION AND EXAMPLES
Let A and B be sets. A binary relation is defined from A to B asas u b s e t
of A × B.
For a single set A, binary relation is defined from A to B asas u b s e to fA
×A
Where A ×Bis cartesian product of sets A and B
For ex ample : Let A={ 1,2} and B={a, b}. Then { (1, a), ( 1,b), ( 2,b )} is
a relation from AtoB.
If (a,b) R then we denote it by aRb
If (a,b) R then we denote it by aRb
In above example 1 R a while 2 R a
2.3PROPERTIES OF RELATIONS
Let A be aset.Let R be a relation defined on A.
There are several properties that are used to classify relations on a
set. We will discuss some important of these here.munotes.in

Page 7

71)Reflexive : A relation R on a set A is called reflexive if (a, a) ∈Rf o r
every element a ∈A.
2) Symmetry : ArelationR on a setAis called symmetric if (b, a) ∈R
whenever (a, b) ∈R, for all a, b ∈A.
3) Transitive :A relation R on a set A is called transitive if whenever (a, b)
∈Ra n d( b ,c ) ∈R,then (a, c) ∈R, for all a, b, c ∈A.
Example :
Consider the following relation on {1, 2, 3, 4}:
1)R={ ( 1 ,1 ) ,( 1 ,2 ) ,( 2 ,1 ) ,( 2 ,2 ) ,( 3 ,4 ) ,( 4 ,1 ) ,( 4 ,4 ) } ,
Then R is reflexive since (1,1),(2,2),(3,3) and (4,4) all belon to R
R is not symmetric as (3,4) ∈Rb u t( 4 , 3 ) R
R is not transitive as (3,4) ∈Ra n d ( 4 , 1 ) ∈Rb u t( 4 , 1 ) R
Whereas if we take R = { {(1, 1), (2, 1), (2, 2), (3, 4), (4,3), (4, 4)} }
R satisfies all three properties .
A relation which satisfies all three properties is called an equivalence
relation.
2.4PARTIAL ORDERING SET
DEFINITION 1 A relation R on a set S is called a partial ordering or
partial order if it is reflexive, antisymmetric, and transitive. A set S
together with a partial ordering R is called a partially ordered set, or poset,
and is denoted by (S, R). Members of S are cal led elements of the poset.
A relation R is antisymmetric when :
for all a, b ∈A, if (a, b) ∈Ra n d( b ,a ) ∈R, then a = b
EXAMPLE 1 Show that the “greater than or equal” relation ( ≥) is a
partial ordering on the set of integers.
Solution :B e c a u s ea ≥af o re v e r yi n t e g e ra , ≥is reflexive.
If a≥ba n db ≥a, then a = b. Hence, ≥is antisymmetric.
Finally, ≥is transitive because a ≥ba n db ≥ci m p l yt h a ta ≥c.
It follows that ≥is a partial ordering on the set of integers and (Z, ≥) is a
poset
EXAMPLE 2 Show that the inclusion relation ⊆is a partial ordering on
the power set of a set S.
Solution :B e c a u s eA ⊆Aw h e n e v e rAi sas u b s e to fS , ⊆is reflexive.
It is antisymmetric because A ⊆Ba n dB ⊆A imply that A = B.
Finally, ⊆is transitive, because A ⊆Ba n dB ⊆C imply that A ⊆C.
Hence, ⊆is a partial ordering on P (S), and (P (S), ⊆) is a poset.munotes.in

Page 8

8DEFINITION 2 The elements a and b of a poset (S, ) are called
comparable if either a b or b a. When a and b are elements of S such that
neither a b nor b a, a and b are called incomparable.
EXAMPLE 5 In the poset (Z+, |), are the integers 3 and 9 comparable?
Are 5 and 7 comparable? Solution: The integers 3 and 9 are comparable,
because 3 | 9. The integers 5 and 7 are incomparable, because 5 | 7 and
7|5 .
The adjective “partial” is used to describe partial orderings because
pairs of elements may be incomparable. When every two elements in the
set are comparable, the relation is called a total ordering
2.5HASSE DIAGRAMS
Many edges in the directed graph for a finite poset do not have to
be shown because they must be present. For instance, consider the directed
graph for the partial ordering {(a, b) | a ≤b} on the set {1, 2, 3, 4}, shown
in Figure 1(a).
Because this relation is a partial ordering, it is reflexive, and its
directed graph has loops at all vertices. Consequently, we do not have to
show these loops because they must be present; in Figure 1(b) loops are
not shown. Because a partial ordering is transitive, we do not have to show
those edges that must be present because of transitivity.
For example, in Figure 1(c) the edges (1, 3), (1, 4), and (2, 4) are
not shown because they must be present. If we assume that all edges are
pointed “upward” (a s they are drawn in the figure), we do not have to
show the directions of the edges; Figure 2(c) does not show directions. In
general, we can represent a finite poset (S, ) using this procedure: Start
with the directed graph for this relation. Because a pa rtial ordering is
reflexive, a loop (a, a) is present at every vertex a.
1.Remove these loops.
2.Next, remove all edges that must be in the partial ordering because of
the presence of other edges and transitivity. That is, remove all edges
(x, y) for w hich there is an element z ∈S such that x ≺za n dz ≺x.
3.Finally, arrange each edge so thatits initial vertex is below its terminal
vertex (as it is drawn on paper).
4.Remove all the arrows on the directed edges, because all edges point
“upward” toward their terminal vertex.
These steps are well defined, and only a finite number of steps
need to be carried out for a finite poset. When all the steps have been
taken, th e resulting diagram contains sufficient information to find the
partial ordering, as we will explain later. The resulting diagram is called
theHasse diagram of poset named after the twentieth -century German
mathematician Helmut Hasse who made extensive us eo ft h e m .L e t( S , ≺)munotes.in

Page 9

9be a poset. We say that an element y ∈S covers an element x ∈S if x ≺y
and there is no element z ∈S such that x ≺z≺y. The set of pairs (x, y)
such that y covers x is called the covering relation of (S, ≺). From the
description o f the Hasse diagram of a poset, we see that the edges in the
Hasse diagram of (S, ≺) are upwardly pointing edges corresponding to the
pairs in the covering relation of (S, ≺). Furthermore, we can recover a
poset from its covering relation, because it is th e reflexive transitive
closure of its covering relation. (Exercise 31 asks for a proof of this fact.)
This tells us that we can construct a partial ordering from its Hasse
diagram.
Figure 1
EXAMPLE 12 Draw the Hasse diagram representing the partial ordering
{(a, b) /a divides b} on{1, 2, 3, 4, 6, 8, 12}.
Solution: Begin with the digraph for this partial order, as shown in Figure
3(a). Remove all loops, as shown in Figure 3(b). Then delete al l the edges
implied by the transitive property. These are (1, 4), (1, 6), (1, 8), (1, 12),
(2, 8), (2, 12), and (3, 12). Arrange all edges to point upward, and delete
all arrows to obtain the Hasse diagram. The resulting Hasse diagram is
shown in Figure 3( c).
Figure 2munotes.in

Page 10

102.6MAXIMUM AND MINIMUM ELEMENTS
Elements of posets that have certain extremal properties are
important for many applications. An element of a poset is called maximal
if it is not less than any element of the poset. That is, a is maximal in the
poset (S, ≺) if there is no b ∈Ss u c ht h a ta ≺b. Similarly, an element of a
poset is called minimal if it is not greater than any element of the poset.
That is, a is minimal if there is no element b ∈S such that b ≺a. Maximal
and minimal elements are easy to spot using a Hasse diagram. They are
the “top” and “bottom” elements in the diagram.
EXAMPLE 1 : Which elements of the poset ({2, 4, 5, 10, 12, 20, 25}, |)
are maximal, and which are minimal? Solution: The Hasse diagram in
Figure 2for this poset shows that the maximal elements are 12, 20, and
25, and the minimal elements are 2 and 5. As this example shows, a poset
can have more than one maximal element and more than one minimal
element. Sometimes there is an element in a poset that is greater than
every other element. Such an element is called the greatest element. That
is, a is the greatest element of the poset (S, ≺)
Lattices
A partially ordered set in which every pai r of elements has both a
least upper bound and a greatest lower bound is called a lattice. Lattices
have many special properties. Furthermore, lattices are used in many
different applications such as models of information flow and play an
important role in Boolean algebra.
EXAMPLE 2 Determine whether the posets represented by each of the
Hasse diagrams in Figure 3are lattices. Solution: The posets represented
by the Hasse diagrams in (a) and (c) are both lattices because in each poset
every pair of elemen ts has both a least upper bound and a greatest lower
bound, as the reader should verify. On the other hand, the poset with the
Hasse diagram shown in (b) is not a lattice, because the elements b and c
have no least upper bound. To see this, note that each of the elements d, e,
and f is an upper bound, but none of these three elements precedes the
other two with respect to the ordering of this poset.
Figure 3munotes.in

Page 11

112.7SUMMARY
Relationships among elements of more than two sets often arise.
For instance, there is a relationship involving the name of a student, the
student’s major, and the student’s grade point average.
Similarly, there is a relationship involving the airline, flight
number, starting point, destination, departure time, and arrival time of a
flight. An example of such a relationship in mathematics involves three
integers, where the first integer is larger than the second integer, which is
larger than the third. Another example is the betweenness relationship
involving points on a line, such that three points are related when the
second point is between the first and the third.
2.8EXERCISE
1. List the ord ered pairs in the relation R fromA = {0, 1, 2, 3, 4} to B = {0,
1, 2, 3}, where (a, b) ∈Rif and only if
a) a = b.
b) a + b = 4.
c) a>b.
d) a | b.
e) gcd(a, b) = 1.
f ) lcm(a, b) = 2.
2. a) List all the ordered pairs in the relationR = {(a, b) | a divi des b} on
the set {1, 2, 3, 4, 5, 6}.
b) Display this relation graphically.
c) Display this relation in tabular form.
3. For each of these relations on the set {1, 2, 3, 4}, decidewhether it is
reflexive, whether it is symmetric, whetherit is antisymmet ric, and
whether it is transitive.
a) {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}
b) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}
c) {(2, 4), (4, 2)}
d) {(1, 2), (2, 3), (3, 4)}
e) {(1, 1), (2, 2), (3, 3),(4, 4)}
f){ ( 1 ,3 ) ,( 1 ,4 ) ,( 2 , 3), (2, 4), (3, 1), (3, 4)}
4. Determine whether the relation R on the set of all peopleis reflexive,
symmetric, antisymmetric, and/or transitive,where (a, b) ∈R if and
only ifmunotes.in

Page 12

12a) a is taller than b.
b) a and b were born on the same day .
c) a has the same first name as b.
d) a and b have a common grandparent.
5. Determine whether the relation R on the set of all Webpages is
reflexive, symmetric, antisymmetric, and/or transitive, where (a, b) ∈R if
and only if
a) everyone who has visite d Web page a has also visitedWeb page b.
b) there are no common links found on both Webpage a and Web page b.
c) there is at least one common link on Web page a andWeb page b
2.9 REFERENCES
1.Discrete Mathematics and Its Applications, Seventh Edition by
Kenneth H. Rosen, McGraw Hill Education(India) Private Limited.
(2011)
2.Norman L. Biggs, Discrete Mathematics, Revised Edition, Clarendon
Press, Oxford 1989.
3.Data Structures Seymour Lipschutz, S chaum’s out lines, McGraw -
Hill Inc.
4.Elements of Discrete Mathematics: C.L. Liu , Tata McGraw -Hill
Edition .
5.Concrete Mathematics (Foundation for Computer Science): Graham,
Knuth, Patashnik Second Edition, Pearson Education.
6.Discrete Mathematics: Semyour Lipschutz, Marc Lipson, Schaum’s
out lines, McGraw -Hill Inc.
7.Foundations in Discrete Mathematics: K.D. Joshi, New Age
Publication, New Delhi.


munotes.in

Page 13

133
RECURRENCE RELATION
Unit Structure: -
3.1 Introduction ,
3.2 Definition and Formulation
3.3 Solving Recurrence Relation
3.3.1 Backtracking
3.3.2 Linear homogeneous recurrence relations with constant
coefficients.
3.3.3 Non Linear Recurrence Relations with Constant
Coefficients.
3.3.4 Generating Functions
3.4Summary
3.5Exercise
3.6References
3.1INTRODUCTION
This chapter is focusing on Recurrence relations and example
3.2 RECURRENCE RELATION
A recurrence relation is an equation that recursively defines a
sequence where the next term is a function of the previous terms
(Expressing F nas some combination of F iwith iExample −Fibonacci series −Fn=Fn−1+Fn−2,T o w e ro fH a n o i −Fn=2F n−1+1
Linear Recurrence Relations
A linear recurrence equation of degree k or order k is a recurrence
equation which is in the format x n=A1xn−1+A2x n−1+A3x n−1+…A kxn−k(An
is a constant and A k≠0) on a sequence of numbers as a first -degree
polynomial.munotes.in

Page 14

14These are some examples of linear recurrence equations
A recurrence relation is an equation that recursively defines a
sequen ce, i.e., each term of the sequence is defined as a function of the
preceding terms. A recursive formula must be accompanied by initial
conditions (information about the beginning of the sequence).The first
method is called backtracking, and consists of ta king a linear recurrence
defining an, and replace the terms a n−1,an−2, . . . with the relation that
defines an, but where n is replaced by n −1, n −2, etc. This is best
illustrated on an example.
A recurrence relation can be used to model various situa tions in
real life like compound interest, algorithms in computer to name a few .
3.3 SOLVING RECURRENCE RELATION
Recurrence relations canbe solved using iteration or some other ad hoc
technique.solving recurrence relation means finding an explicit formu la .
Following methods can be used :
1B a c k t r a c k i n g
2 Linear method
3. Generating functions
3.3.1BACKTRACKING
In this type we use recurrence relation torepeatedly to express nthin
terms of previous terms ofthe sequence till we reach initial condit ion or
are able to identify a pattern
Example . Consider the linear recurrence
an=an−1+3 ,a 1=2 .
Then a n−1=an−2+3a n−2=an−3+3a n−3=an−4+3a n ds oo na n ds of o r t h .
Therefore a n=an−1+3=( a n−2+3 )+3=a n−2+2· 3=( a n−3+3)+6=a n−3
+3·3=...=a 1+3 ( n −1).
The last equality follows because a generic term is of the form a n−i+3 i ,
therefore when n −i = 1,. By plugging the initial condition, we conclude
an=2+3 ( n −1).
Once the solution has been found, you may w onder how to check whether
this is the right answer. One way to do it is by proving it by induction!munotes.in

Page 15

153.3.2 LINEAR HOMOGENEOUS RECURRENCE RELATIONS
WITH CONSTANT COEFFICIENTS
A linear homogeneous recurrence relation of degree k with
constant coefficients i s a recurrence relation of the form a n=c1an−1+c2an−2
+· · ·+ c kan−k,where c 1,c2,...,c kare real numbers, and c k≠0
The recurrence relation in the definition is linear because the right -
hand side is a sum of previous terms of the sequence each multiplied by a
function of n. The recurrence relation is homogeneous because no terms
occur that are not multiples of the a js. The coefficients of the terms of the
sequence are all constants, rather than functions that depend on n. The
degree is k because a nis expressed in terms of the previous k terms of the
sequence.
A consequence of the second principle of mathematical induction
is that a sequence satisfying the recu rrence relation in the definition is
uniquely determined by this recurrence relation and the k initial conditions
a0=C 0,a1=C 1,...,a k−1=C k−1.
EXAMPLE The recurrence relation Pn = (1.11)P n−1is a linear
homogeneous recurrence relation of degree one.
The recurrence relation f n=fn−1+fn−2is a linear homogeneous recurrence
relation of degree two.
The recurrence relation a n=a n−5is a linear homogeneous recurrence
relation of degree five.
Consider linear homogeneous relation of degree d is of th ef o r m
an=c1an-1+c2an-2+…..+c dan-d
We first form characteristic equation of the recurrence relation. The
solutions of this equation are called the characteristic roots of the
recurrence relation. These characteristic roots can be used to give an
explicit formula for all the solutions of there currence relation.
Three cases may occur while finding the roots −
Case 1 −If this equation factors as (x −x1)(x−x1)=0 and it produces two
distinct real roots x 1and x 2, then Fn=axn
1+bxn
2is the s olution. [Here, a
and b are constants]
Case 2 −If this equation factors as (x −x1)2=0 and it produces single real
root x 1, then F n=axn
1+bnxn
1is the solution.
Case 3 −If the equation produces two distinct complex roots, x1 and x2 in
polar form x1=r ∠θand x2=r ∠(−θ), then Fn=rn(acos(nθ)+bsin(nθ)) is the
solution.munotes.in

Page 16

16Example The Fibonacci sequence f n=f n−1+f n−2is a homogeneous
relation. Let us compute its characteristic equation:
xn−xn−1−xn−2=0 ⇐⇒xn−2
(x2−x−1) = 0
therefore x2−x−1 = 0 is the characteristic equation.
Let us focus on quadratic characteristic equations, that is of the formx2−
c1x−c2= 0which corresponds to linear recurrences of the form
an=c1an−1+c2an−2.
Suppose that x2−c1x−c2= 0 has two distinct real roots s 1,s2, then
s2
1−c1s1−c2=0 ,s2
2−c1s2−c2=0 .
Thereforesn1 −c1sn−11−c2sn−2=0 ,s n 2 −c1sn−12−c2sn−2=0
and we have that if s is a solution of x2 −c1x−c2 = 0 then snis a solution
ofan = c1an −1+c2an −2. This te lls us that solutions of an are composed of
sn1, sn2.
Example :
Solve the recurrence relation F n=5F n−1−6Fn−2where F 0=1 and F 1=4
Solution
The characteristic equation of the recurrence relation is −
x2−5x+6=0,
So, (x −3)(x−2)=0
Hence, the roots are −
x1=3 and x 2=2
The roots are real and distinct. So, this is in the form of case 1
Hence, the solution is −
Fn=axn
1+bxn
2
Here, Fn=a3n+b2n(As x 1=3 and x 2=2)
Therefore,
1=F 0=a30+b20=a+b
4=F 1=a31+b21=3a+2b
Solving these two equations, we get a=2 and b= −1
Hence, the final solution is −
Fn=2.3n+(−1).2n=2.3n−2n
Note the term ”composed” is used, because if a sequence a0nbalso
satisfies therecurrence of an, then a n+a ’ nsatisfies the recurrence of an as
well, as doesmultiples of a nmunotes.in

Page 17

173.3.3 GENERATING FUNCTIONS
The generating function for the sequence a 0,a1,...,a k ,... of real
numbers is the infiniteseries
G(x) = a0 + a1x +· · · +akxk +· · ·
We can find the solution to a recurrence relation and its initial
conditions by finding an explicit formula for the ass ociated generating
function.
3.3.4 NON LINEAR NON HOMOGENEOUS RECURRENCE
RELATIONS WITH CONSTANT COEFFICIENTS
We have seen how to solve linear homogeneous recurrence
relations with constant coefficients. Is there a relatively simple technique
for solving a linear, but not homogeneous, recurrence relation with
constant coefficients, such as a n=3 a n−1+2 n? We will see that the answer
is yes for certain families of such recurrence relations. The recurrence
relation an = 3a n−1+ 2n is an example of a linear nonhomogeneous
recurrence relation with constant coefficients, that is, a recurrence relation
of the form an = c 1an−1+c2an−2+···+ c kan−k+F( n ) ,
where c1, c2,...,ck are real numbers and F (n) is a function not identically
zero depending only on n. The recurrence relation an = c 1an−1+c2an−2+· · ·+
ckan−kis called the associated homogeneous recurrence relation. It plays an
important role in the solution of the nonhomogeneous recurrence relation.
Merge Sort The merge sort algorithm (introduced in Section 5.4)
splits a list to be sorted with n items, where n is even, into two lists with
n/2 elements each, and uses fewer than n comparisons to merge the two
sorted lists of n/2 items each into one sorted list. Consequently, the
number of comparisons us ed by the merge sort to sort a list of n elements
is less than M(n), where the function M(n) satisfies the divide -and-
conquer recurrence relation M(n) = 2M(n/2) + n.
Tower of Honoi
The Tower of Hanoi A popular puzzle of the late nineteenth
century invente d by the French mathematician Édouard Lucas, called the
Tower of Hanoi, consists of three pegs mounted on a board together with
disks of different sizes. Initially these disks are placed on the first peg in
order of size, with the largest on the bottom (as shown in Figure 2). The
rules of the puzzle allow disks to be moved one at a time from one peg to
another as long as a disk is never placed on top of a smaller disk. The goal
of the puzzle is to have all the disks on the second peg in order of size,
with the largest on the bottom. Let H ndenote the number of moves needed
to solve the Tower of Hanoi problem with n disks. Set up a recurrence
relation for the sequence {H n}. Solution: Begin with n disks on peg 1. We
can transfer the top n −1 disks, following the rules of the puzzle, to peg 3
using Hn −1 moves (see Figure 3 for an illustration of the pegs and disks at
this point). We keep the largest disk fixed during these moves. Then, wemunotes.in

Page 18

18use one move to transfer the largest disk to the second peg. We can
trans fer the n −1 disks on peg 3 to peg 2 using Hn −1 additional moves,
placing them on top of the largest disk, which always stays fixed on the
bottom of peg 2. Moreover, it is easy to see that the puzzle cannot be
solved using fewer steps. This shows that H n=2Hn−1+ 1. The initial
condition is H 1= 1, because one disk can be transferred from peg 1 to peg
2, according to the rules of the puzzle, in one move
We can use an itera tive approach to solve this recurrence relation. Note
that H n=2 H n−1+1=2 ( 2 H n−2+1 )+1=2 2 H n−2+2+1=2 2 ( 2 H n−3+1 )+
2+1=2 3 H n−3+2 2+2+1...=2 n −1H1+2 n−2+2 n −3+ · · · +2+1=
2n−1+2 n −2+ · · · +2+1=2 n −1. We have used the recur rence relation
repeatedly to express Hn in terms of previous terms of the sequence. In the
next to last equality, the initial condition H1 = 1 has been used. The last
equality is based on the formula for the sum of the terms of a geometric
series, which ca n be found in Theorem 1 in Section 2.4. The iterative
approach has produced the solution to the recurrence relation H n=2 H n−1
+ 1 with the initial condition H1 = 1. This formula can be proved using
mathematical induction. This is left for the reader as Ex ercise 1. A myth
created to accompany the puzzle tells of a tower in Hanoi where monks
are transferring 64 gold disks from one peg to another, according to the
rules of the puzzle. The myth says that the world will end when they finish
the puzzle. How long after the monks started will the world end if the
monks take one second to move a disk? From the explicit formula, the
monks require264−1 = 18,446,744,073,709,551,615 moves to transfer the
disks. Making one move per second, it will take them more than 500munotes.in

Page 19

19billion years to complete the transfer, so the world should survive a while
longer than it already has
3.4SUMMARY
This chapter give s introductory view about recurrence relation and
also explains and demonstrates some basic examples.
3.5EXERCISE
1. Use mathematical induction to verify the formula derivedin Example 2
for the number of moves required to complete the Tower of Hanoi
puzzle.
2. a) Find a recurrence relation for the number of permutations of a set
with n elements.
b) Use this recurrence relation to find the number of permutations of a set
with n elements using iteration.
3. A vending machine dispensing books of stamps accepts only one -dollar
coins, $1 bills, and $5 bills.
a) Find a recurrence relation for the number of ways to deposit n dollars in
the vending machine, where the order in which the coins and bills are
deposited matters.
b) What are the initial conditions?
c) How many ways are there to deposit $10 for a bookof stamps?
4. A country uses as currency coins with values of 1 peso,2 pesos, 5 pesos,
and 10 pesos and bills with values of5 pesos, 10 pesos, 20 pesos, 50
pesos, and 100 pesos. Finda recurrence relation for the number of
ways to pay a billof n pesos if the order in which the coins and bills
arepaid matters
3.6 REFERENCES
1. Discrete Mathematics and Its Applications, Seventh Edition by Kenneth
H. Rosen, McGraw Hill Education(India) Private Limited. (201 1)
2. Norman L. Biggs, Discrete Mathematics, Revised Edition, Clarendon
Press, Oxford 1989.
3. Data Structures Seymour Lipschutz, Schaum’s out lines, McGraw -Hill
Inc.munotes.in

Page 20

204. Elements of Discrete Mathematics: C.L. Liu , Tata McGraw -Hill
Edition .
5. Concrete Mathematics (Foundation for Computer Science): Graham,
Knuth, Patashnik Second Edition, Pearson Education.
6. Discrete Mathematics: Semyour Lipschutz, Marc Lipson, Schaum’s out
lines, McGraw -Hill Inc.
7. Foundations in Discrete Mathematics: K.D. Joshi, Ne wA g e
Publication, New Delhi.


munotes.in

Page 21

21Unit -II
Counting Principles, Languages and Finite
State Machine
4
PERMUTATIONS AND COMBINATIONS
Unit Structure: -
4.1 Introduction.
4.2 Permutation and combinations.
4.3 Binomial number and combinations
4.3.1 Pascal’s Identity .
4.3.2Vandermonde’s Identity .
4.4 Permutation and combinations with indistinct objects
4.5S u m m a r y
4.6 Exercise
4.7R e f e r e n c e s
4.1INTRODUCTION
Combinator icsisavery important part in discrete mathematics. It
is used to solve many mathematical and general problems .
4.2 PERMUTATION AND COMBINATIONS: -
Many counting problems can be solved by finding the number of
ways to arrange a specified number of distinct elements of a set of a
particular size, where the order of these elements matters. Many other
counting problems can be solved by finding the number of ways to select
particular number of elements from a set of a particular size ,w h e r et h e
order of the elements selected does not matter. For example, in how many
ways can we select three students from a group of five students to stand in
line for a picture? How many different committees of three students can be
formed from a group of four students? In this section we will develop
methods to answer questions such as these.
A permutation of a set of distinct objects is an ordered arrangement
of these objects. We also are interested in ordered arrangements of some
of the elements of a set. An ordered arrangement of r elements of a set is
called an r -permutation.munotes.in

Page 22

22Let S = {1, 2, 3}. The ordered arrangement 3, 1, 2 is a permutation
of S. The ordered arrangement 3, 2 is a 2 -permutation of S. The number of
r-permutations of a set with n ele ments is denoted by P (n, r). We can find
P (n, r) using the product rule.
P(n,r) = n! /(n -r)!
Problem 1: How many ways are there to select a first -prize winner, a
second -prize winner, and a third -prize winner from 100 different people
who have entered a contest?
Because it matters which person wins which prize, the number of
ways to pick the three prize winners is the number of ordered selections of
three elements from a set of 100 elements, that is, the number of 3 -
permutations of a set of 100 elemen ts. Consequently, the answer is
P( 1 0 0 ,3 )=1 0 0·9 9·9 8=9 7 0 , 2 0 0 .
Problem 2: Suppose that there are eight runners in a race. The winner
receives a gold medal, the second place finisher receives a silver medal,
and the third -place finisher receives a b ronze medal. How many different
ways are there to award these medals, if all possible outcomes of the race
can occur and there are no ties?
Solution: The number of different ways to award the medals is the
number of 3 -permutations of a set with eight elem ents. Hence, there are P
(8, 3) = 8 · 7 · 6 = 336 possible ways to award the medals.
Problem 3: Suppose that a saleswoman has to visit eight different cities.
She must begin her trip in a specified city, but she can visit the other seven
cities in any ord er she wishes. How many possible orders can the
saleswoman use when visiting these cities?
Solution: The number of possible paths between the cities is the number
of permutations of seven elements, because the first city is determined, but
the remaining s even can be ordered arbitrarily. Consequently, there are 7!
= 7 · 6 · 5 · 4 · 3 · 2 · 1 = 5040 ways for the saleswoman to choose her tour.
If, for instance, the saleswoman wishes to find the path between the cities
with minimum distance, and she computes t he total distance for each
possible path, she must consider a total of 5040 paths!
Problem 4: How many permutations of the letters ABCDEFGH contain
the string ABC ?
Solution: Solution: Because the letters ABC must occur as a block, we
can find the answer by finding the number of permutations of six objects,
namely, the block ABC and the individual letters D, E, F, G, and H.
Because these six objects can occur in any order, there are 6! = 720
permutations of the letters ABCDEFGH in which ABC occurs as a bl ock.munotes.in

Page 23

23Combinations
An r-combination of elements of a set is an unordered selection of
r elements from the set. Thus, an r -combination is simply a subset of the
set with r elements. It is denoted by C(n,r) and given by n! /[r! (n -r)!]
Example 1: Let S be t he set {1, 2, 3, 4}. Then {1, 3, 4} is a 3 -combination
from S. (Note that {4, 1, 3} is the same 3 -combination as {1, 3, 4},
because the order in which the elements of a set are listed does not
matter.)
Example 2: -How many poker hands of five cards can be dealt from a
standard deck of 52 cards? Also, how many ways are there to select 47
cards from a standard deck of 52 cards?
Solution: Because the order in which the five cards are dealt from a deck
of 52 cards does not matter, there are
C(52, 5) =
different hands of five cards that can be dealt. To compute the value of
C(52, 5), first divide the numerator and denominator by 47! to obtain
C(52, 5) =
This expression can be simplified by first dividing the factor 5 in the
denominator into the factor 50 in the numerator to obtain a factor 10 in the
numerator, then dividing the factor 4 in the denomi nator into the factor 48
in the numerator to obtain a factor of 12 in the numerator, then dividing
the factor 3 in the denominator into the factor 51 in the numerator to
obtain a factor of 17 in the numerator, and finally, dividing the factor 2 in
the deno minator into the factor 52 in the numerator to obtain a factor of 26
in the numerator. We find that C(52, 5) = 26 · 17 · 10 · 49 · 12 =
2,598,960.
Consequently, there are 2,598,960 different poker hands of five
cards that can be dealt from a standard deck of 52 cards.
Example 3: -A group of 30 people have been trained as astronauts to go
on the first mission to Mars. How many ways are there to select a crew of
six people to go on this mission (assuming that all crew members have the
same job)?
Solution: -The number of ways to select a crew of six from the pool of 30
people is the number of 6 -combinations of a set with 30 elements, because
the order in which these people are chosen does not matter., the number of
such combinations is
C(30, 6) =
=
=5 9 3 , 7 7 5 .munotes.in

Page 24

24Example 4 : How many bit strings of length n contain exactly r 1s?
Solution : -The positions of r 1s in a bit string of length n form an r -
combination of the set {1, 2, 3,...,n}. Hence, there are C(n, r) bit strings of
length n that contain exactly r 1s
Binomial Number: -
Binomial number is a number oft h ef o r m
,where
,
and
areintegers . Binomial numbers can be factored algebraically as
(1)
for all
,
(2)
for
odd, and
(3)
for all positive integers
. For example,
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
and
(13)
(14)
(15)
(16)
(17)
(18)
(19)
(20)
(21)
Rather surprisingly, the number of factors of
with
and
symbolic and
a positive integer is given by
,w h e r e
is the
number of divisors of
and
is the divisor function. The first few
terms are therefore 1, 2, 2, 3, 2, 4, 2, ...
Pascal’s Ide ntity and Triangle
The binomial coefficients satisfy many different identities. We
introduce one of the most important of these now.
C(n+1,k) = C(n,k) + C(n,k -1)
Proof: We will use a combinatorial proof. Suppose that T is a set
containing n + 1 element s. Let a be an element in T , and let S = T −{a}.munotes.in

Page 25

25Note that there are n+1 k subsets of T containing k elements. However, a
subset of T with k elements either contains a together with k −1 elements
of S, or contains k elements of S and does not contain a .B e c a u s et h e r ea r e
nk−1 subsets of k −1 elements of S, there are n k −1 subsets of k
elements of T that contain a. And there are n k subsets of k elements of T
that do not contain a, because there are n k subsets of k elements of S.
Consequently,
4.3.1PASCAL’S TRIANGLE.
Remark: Pascal’s identity, together with the initial conditions n 0 = n n =
1 for all integers n, can be used to recursively define binomial coefficients.
This recursive definition is useful in the computation of binomial
coeff icients because only addition, and not multiplication, of integers is
needed to use this recursive definition. Pascal’s identity is the basis for a
geometric arrangement of the binomial coefficients in a triangle, as shown
in Figure 1. The nth row in the t riangle consists of the binomial
coefficients n k , k = 0, 1, . . . , n. This triangle is known as Pascal’s
triangle. Pascal’s identity shows that when two adjacent binomial
coefficients in this triangle are added, the binomial coefficient in the next
rowbetween these two coefficients is produced
4.3.2 VANDERMONDE’S IDENTITY
Definition : -Let m, n, and r be nonnegative integers with r not exceeding
either m or n. Then C(m+n ,r)=∑(k=0 to r) C( m,r–k)C(n,k)
Rema rk:This identity was discovered by mathematician Alexandre -
Théophile Vandermonde in the eighteenth century.
Proof: Suppose that there are m items in one set and n items in a second
set. Then the total number of ways to pick r elements from the union of
these sets is m + n r . Another way to pick r elements from the union is to
pick k elements from the second set and then r −k elements from the first
set, where k is an integer with 0 ≤k≤r. Because there are n k ways to
choose k elements from the sec ond set and m r −kw a y s t o c h o o s e r −k
elements from the first set, the product rule tells us that this can be done in
mr−k n k ways. Hence, the total number of ways to pick r elementsmunotes.in

Page 26

26from the union also equals r k = 0 m r −knk .W eh a v ef o u n d two
expressions for the number of ways to pick r elements from the union of a
set with m items and a set with n items. Equating them gives us
Vandermonde’s identity.
4.4PERMUTATION AND COMBINATIONS WITH
INDISTINCT OBJECTS
Concept of permutation and combination can be generalized as follows :
The number of r -permutations of a set of n objects with repetition allowed
is nr.
There are C(n + r −1, r) = C(n + r −1, n−1) r-combinations from a set
with n elements when repeti tion of elements is allowed.
4.5SUMMARY
This Chapter is focused on basic counting principles like
permutation and Combin ation.
4.6 EXERCISE
1. List all the permutations of {a, b, c}.
2. How many different permutations are there of the set{ a, b, c, d, e, f, g}?
3. How many permutations of {a, b, c, d, e, f, g} end witha?
4. How many permutations of the letters ABCDEFG contain
a) the string BCD?
b) the string CFGA?
c) the strings BA and GF?
d) the strings ABC and DE?
e) the strings ABC and CDE?
f ) the strings CBA and BED?
5. How many permutations of the letters ABCDEFGH contain
a) the string ED?
b) the string CDE?
c) the strings BA and FGH?
d) the strings AB, DE, and GH?
e) the strings CAB and BED?
f) the strings BCA and ABF?munotes.in

Page 27

276. How many ways are there for eight men and five women to stand in a
line so that no two women stand next to each other? [Hint: First position
the men and then consider possible positions for the women.]
7. How many ways are there for 10 women and six men to stand in a line
so that no two men stand next to each other? [Hint: First position the
women and then consider possible positions for the men.]
8. One hundred tickets, numbered 1, 2, 3,..., 100, are sold to 100 different
people for a drawi ng. Four different prizes are awarded, including a grand
prize (a trip to Tahiti). How many ways are there to award the prizes if
a) there are no restrictions?
b) the person holding ticket 47 wins the grand prize?
c) the person holding ticket 47 wins one o f the prizes?
d) the person holding ticket 47 does not win a prize?
e) the people holding tickets 19 and 47 both win prizes?
f ) the people holding tickets 19, 47, and 73 all winprizes?
g) the people holding tickets 19, 47, 73, and 97 all winprizes?
h) none of the people holding tickets 19, 47, 73, and 97wins a prize?
i) the grand prize winner is a person holding ticket 19 ,47, 73, or 97?
j) the people holding tickets 19 and 47 win prizes, butthe people
holding tickets 73 and97 do not win prizes?
4.7REFERENCES
1. Discrete Mathematics and Its Applications, Seventh Edition by Kenneth
H. Rosen, McGraw Hill Education(India) Private Limited. (2011)
2. Norman L. Biggs, Discrete Mathematics, Revised Edition, Clarendon
Press, Oxford 1989.
3. Data Structures Seymour Lipschutz, Schaum’s out lines, McGraw -Hill
Inc.
4. Elements of Discrete Mathematics: C.L. Liu , Tata McGraw -Hill
Edition .
5. Concrete Mathematics (Foundation for Computer Science): Graham,
Knuth, Patashnik Second Edition,Pearson Education.
6. Discrete Mathematics: SemyourLipschutz, Marc Lipson, Schaum’s out
lines, McGraw -Hill Inc.
7. Foundations in Discrete Mathematics: K.D. Joshi, New Age
Publication, New Delhi.
munotes.in

Page 28

285
COUNTING PRINCIPLES, LANGUAGES
AND FINITE STATE MACHINE
Unit Structure: -
5.1 Introduction.
5.2 Basic Counting Principles
5.3 Inclusion Exclusion
5.4 Tree Diagrams
5.5 Summary
5.6 Exercise
5.7 References
5.1INTRODUCTION
Suppose that a password on a computer system consists of six,
seven, or eight characters. Eachof these characters must be a digit or a
letter of the alphabet. Each password must contain at leastone digit. How
many such passwords are there? The techniques needed to answer this
questionand a wide variety of other counting problems will be introduced
in this section .
5.2 BASIC COUNTING PRINCIPLES
There are two basic counting principles Product rule and Sum rule
The product rule applies when a procedure is made up of separate tasks.
THE PRODUCT RULE Suppose that a procedure can be broken down
into a sequence of two tasks. If there are n1 ways to do the first task and
for each of these ways of doing the first task, there are n2 ways to do the
second task, then there are n1n2 ways to do the procedure
EXAMPLE 1 A new company with just two employees, Sanchez and
Patel, rents a floor of a building with 12 offices. How many ways are there
to assign different offices to these two employees?
Solution: The procedure of assigning offices to these two employees
consists of assigning an office to Sanchez, which can be done in 12 ways,
then assigning an office to Patel different from the office assigned tomunotes.in

Page 29

29Sanchez, which can be done in 11 ways. By the product rule, there are 12 ·
11= 132 ways to assign offices to these two employees.
EXAMPLE 2 The chairs of an auditorium are to be labeled with an
uppercase English letter followed by a positive integer not exceeding 100.
What is the largest number of chairs that can be labeled differe ntly?
Solution: The procedure of labeling a chair consists of two tasks, namely,
assigning to the seat one of the 26 uppercase English letters, and then
assigning to it one of the 100 possible integers. The product rule shows
that there are 26 · 100 = 2600 different ways that a chair can be labeled.
Therefore, the largest number of chairs that can be labeled differently is
2600
THE SUM RULE If a task can be done either in one of n1 ways or in one
of n2 ways, where none of the set of n1 ways is the same as a ny of the set
of n2 ways, then there are n1 + n2 ways to do the task.
EXAMPLE 3Suppose that either a member of the mathematics faculty or
a student who is a mathematics major is chosen as a representative to a
university committee. How many different choi ces are there for this
representative if there are 37 members of the mathematics faculty and 83
mathematics majors and no one is both a faculty member and a student?
Solution: There are 37 ways to choose a member of the mathematics
faculty and there are 83 ways to choose a student who is a mathematics
major. Choosing a member of the mathematics faculty is never the same
as choosing a student who is a mathematics major because no one is both a
faculty member and a student. By the sum rule it follows that the re are 37
+ 83 = 120 possible ways to pick this representative.
5.3 INCLUSION EXCLUSION
The subtraction rule is also known as the principle of inclusion –
exclusion, especially when it is used to count the number of elements in
the union of two sets. Suppo se that A1 and A2 are sets. Then, there are
|A1| ways to select an element from A1 and |A2| ways to select an element
from A2. The number of ways to select an element from A1 or from A2,
that is, the number of ways to select an element from their union, is the
sum of the number of ways to select an element from A1 and the number
of ways to select an element from A2, minus the number of ways to select
an element that is in both A1 and A2. Because there are|A1 ∪A2|ways to
select an element in either A1 or in A2, and |A1 ∩A2| ways to select an
element common to both sets, we have |A1 ∪A2| = |A1| + |A2| −|A1∩
A2|.munotes.in

Page 30

305.4TREE DIAGRAMS
Counting problems can be solved using tree diagrams. A tree
consists of a root, a number of branches leaving the root, and possible
additional branches leaving the endpoints of other branches. To use trees
in counting, we use a branch to represent each possible choice. We
represent the possible outcomes by the leaves, which are the endpoints of
branches not having other branc hes starting at them.
Figure 1
EXAMPLE 4How many bit strings of length four do not have two
consecutive 1s?
Solution: The tree diagram in Figure 1displays all bit strings of length
four without two consecutive 1s. We see that there are eight bit strings of
length four without two consecutive 1s.
The Pigeonhole Principle:
Suppose that a flock of 20 pigeons flies into a set of 19 pigeonholes to
roost. Because there are 20 pigeons but only 19 pigeonholes, a least one of
these 19 pigeonholes must have at least two pigeons in it. To see why this
is true, note that if each pigeonhole had at most one pigeon in it, at most
19 pigeons, one per hole, could b e accommodated. This illustrates a
general principle called the pigeonhole principle, which states that if there
are more pigeons than pigeonholes, then there must be at least one
pigeonhole with at least two pigeons in it (see Figure 2). Of course, this
principle applies to other objects besides pigeons and pigeonholes.
THE PIGEONHOLE PRINCIPLE If k is a positive integer and k + 1 or
more objects are placed into k boxes, then there is at least one box
containing two or more of the objects.munotes.in

Page 31

31
Figure 2
Proof: We prove the pigeonhole principle using a proof by contraposition.
Suppose that none of the k boxes contains more than one object. Then the
total number of objects would be at most k.
This is a contradiction, because there are at least k + 1 objects.
The pigeonhole principle is also called the Dirichlet drawer principle, after
the nineteenth century German mathematician G. Lejeune Dirichlet, who
often used this principle in his work.
(Dirichlet was not the first person to use this principle; a demonstration
that there were at least two Parisians with the same number of hairs on
their heads dates back to the 17th century) It is an important additional
proof technique supplementing those w e have developed in earlier
chapters. We introduce it in this chapter because of its many important
applications to combinatorics.
We will illustrate the usefulness of the pigeonhole principle. We first show
that it can be used to prove a useful corollary about functions
EXAMPLE 1 Among any group of 367 people, there must be at least two
with the same birthday, because there are only 366 possible birthdays.
EXAMPLE 2 In any group of 27 English words, there must be at least two
that begin with the same lett er,because there are 26 letters in the English
alphabet.
5.5 SUMMARY
This section is focused on Tree structure and Inclusion exclusion
principal with variety of examples.
5.6 EXERCISE
1. There are 18 mathematics majors and 325 computer science majors a ta
college.munotes.in

Page 32

32a) In how many ways can two representatives be picked so that one is a
mathematics major and the other is a computer science major?
b) In how many ways can one representative be picked who is either a
mathematics major or a computer science major?
2. An office building contains 27 floors and has 37 officeson each floor.
How many offices are in the building?
3. A multiple -choice test contains 10 questions. There arefour possible
answers for each question.
a) In how many ways can a student answer the questionson the test if the
student answers every question?
b) In how many ways can a student answer the questionson the test if the
student can leave answers blank?
4. A particular brand of shirt comes in 12 colors, has a male version and a
female version, and comes in three sizes for each sex. How many
different types of this shirt a remade?
5. Six different airlines fly from New York to Denver andseven fly from
Denve r to San Francisco. How many different pairs of airlines can you
choose on which to booka trip from New York to San Francisco via
Denver, when you pick an airline for the flight to Denver and an
airline for the continuation flight to San Francisco?
6. Ther e are four major auto routes from Boston to Detroit and six from
Detroit to Los Angeles. How many major auto routes are there from
Boston to Los Angeles via Detroit?
7. How many different three -letter initials can people have?
8. How many different three -letter initials with none of the letters repeated
can people have?
9. How many different three -letter initials are there that begin with an A?
10. How many bit strings are there of length eight?
11. How many bit strings of length ten both begin and end with a1 ?
12. How many bit strings are there of length six or less, not counting the
empty string?
13. How many bit strings with length not exceeding n, wheren is a positive
integer, consist entirely of 1s, not counting the empty string?
14. How many bit strin gs of length n, where n is a positive integer, start
and end with 1s?
15. How many strings are there of lowercase letters of length four or less,
not counting the empty string?
16. How many strings are there of four lowercase letters thathave the letter
xin them?munotes.in

Page 33

335.7 REFERENCES
1. Discrete Mathematics and Its Applications, Seventh Edition by Kenneth
H. Rosen, McGraw Hill Education(India) Private Limited. (2011)
2. Norman L. Biggs, Discrete Mathematics, Revised Edition, Clarendon
Press, Oxford 1989.
3. Data Structures Seymour Lipschutz, Schaum’s out lines, McGraw -Hill
Inc.
4. Elements of Discrete Mathematics: C.L. Liu , Tata McGraw -Hill
Edition .
5. Concrete Mathematics (Foundation for Computer Science): Graham,
Knuth, Patashnik Second Edition,Pears on Education.
6. Discrete Mathematics: SemyourLipschutz, Marc Lipson, Schaum’s out
lines, McGraw -Hill Inc.
7. Foundations in Discrete Mathematics: K.D. Joshi, New Age
Publication, New Delhi.

munotes.in

Page 34

346
COUNTING PRINCIPLES, LANGUAGES
AND FINITE STATE MACHINE
Unit Structure: -
6.1 Introduction.
6.2 Languages and Grammars.
6.3 Phrase -Structure Grammars.
6.4 Types of Phrase -Structure Grammars
6.5 Finite -State Machines with Output
6.6 Finite -State Automata
6.7 Regular Sets and Regular Grammars
6.8 Turing machine
6.9 Godel Numbers
6.10 Summary
6.11 Exercise
6.12 References
6.1 INTRODUCTION
This chapter is mainly focused on Finite state machines.
6.2 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 article the and the
noun frog, followed by a verb phrase, writes neatly, 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 its 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 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 naturalmunotes.in

Page 35

35language, 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.
We will desc ribe the sentences of a formal language using a
grammar. The use of grammars helps when we consider the two classes of
problems that arise most frequently in applications to programming
languages: (1) How can we determine whether a combination of words is a
valid sentence in a formal language? (2) How can we generate the valid
sentences of a formal language? Before giving a technical definition of a
grammar, we will describe an example of a grammar that generates a
subset of English. This subset of English is defined using a list of rules
that describe how a valid sentence can be produced. We specify that
1.asentence is made up of a noun phrase followed by a verb phrase ;
2.anoun phrase is made up of an article followed by an adjective
followed by a noun ,or
3.anoun phrase is made up of an article followed by a noun ;
4.averb phrase is made up of a verb followed by an adverb ,o r
5.averb phrase is made up of a verb;
6.anarticle isa,o r
7.anarticle isthe;
8.anadjective islarge ,o r
9.anadjective ishungry ;
10.anoun israbbit ,o r
11.anoun ismathematician ;
12.averb iseats,o r
13.averb ishops ;
14.anadverb isquickly ,o r
15.anadverb iswildly
6.3 PHRASE -STRUCTURE GRAMMARS
DEFINITION 1 A vocabulary (or alphabet) V is a finite, nonempty 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, denoted by λ, is
the string containing no symbols. The set of all words over V is denoted
byV∗. A language over V is a su bset 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. Languages can be
specified in various ways. One w ay is to list all the words in the language.
Another is to give some criteria that a word must satisfy to be in the
language. In this section, we describe another important way to specify a
language, namely, through the use of a grammar, such as the set of rules
we gave in the introduction to this section. A grammar provides a set of
symbols of various types and a set of rules for producing words. Moremunotes.in

Page 36

36precisely, a grammar has a vocabulary V , which is a set of symbols used
to derive members of the language .
Some of the elements of the vocabulary cannot be replaced by
other symbols. These are called terminals, and the other members of the
vocabulary, which can be replaced by other symbols, are called
nonterminals. The sets of terminals and nonterminals are u sually denoted
by T and N, respectively. In the example given in the introduction of the
section, the set of terminals is {a, the, rabbit, mathematician, hops, eats,
quickly, wildly}, and the set of nonterminals is {sentence, noun phrase,
verb phrase, adje ctive, article, noun, verb, adverb}. There is a special
member of the vocabulary called the start symbol, denoted by S, which is
the element of the vocabulary that we always begin with. In the example
in the introduction, the start symbol is sentence. The rules that specify
when we can replace a string from V ∗, the set of all strings of elements in
the vocabulary, with another string are called the productions of the
grammar. We denote by z 0→z1the production that specifies that z0 can
be replaced by z 1within a string. The productions in the grammar given in
the introduction of this section were listed. The first production, written
using this notation, is sentence →noun phrase verb phrase. We
summarize this terminology in Definition 2.
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 nonterminal symbol s. Every
production in P must contain at least one nonterminal on its left side.
EXAMPLE 1 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 phrasestructure grammar.
6.4 TYPES OF PHRASE -STRUCTURE GRAMMARS
A type 0 grammar has no restrictions on its productions. A type 1
grammar can have productions of the form w1 →w2, where w1 = lAr and
w2 = lwr, where A is a nonterminal symbol, l and r are strings of zero or
more terminal or nonterminal symbols, and w is a nonempty string of
terminal or nonterminal symbols. It can also have the production S → λ as
long as S does not appear on the right -hand side of any other production.
A type 2 grammar can have productions only of the form w1 →w2, where
w1 is a single symbol that is not a terminal symbol. A type 3 grammar can
have productions only of the form w1 →w2 with w1 = A and either w2 =
aB or w2 = a, where A and B are nonterminal symbols and a is a terminal
symbol, or with w1 = S and w2 = λ.munotes.in

Page 37

37Type 2 grammars are called context -free grammars because a
nonterminal symbol that is the left side of a production can be replaced in
a string whenever it occurs, no matter what else is in the string.A language
generated by a type 2 grammar is called a context -free language. When
there is a production of the form lw 1r→lw2r (but not of the form w 1→
w2), the grammar is c alled type 1 or context -sensitive because w1 can be
replaced by w2 only when it is surrounded by the strings l and r. A
language generated by a type 1 grammar is called a context -sensitive
language. Type 3 grammars are also called regular grammars. A langu age
generated by a regular grammar is called regular. Section 13.4 deals with
the relationship between regular languages and finite -state machines.
6.5 FINITE -STATE MACHINES WITH OUTPUT
DEFINITION 1 A finite -state machine M = (S, I, O, f, g, s 0) consist so fa
finite set S of states, a finite input alphabet I, a finite output alphabet O, a
transition function f that assigns to each state and input pair a new state, an
output function g that assigns to each state and input pair an output, and an
initial st ate s 0
Let M = (S, I, O, f, g, s 0) be a finite -state machine. We can use a state table
to represent the values of the transition function f and the output function
g for all pairs of states and input. Wepreviously constructed a state table
for the vending machine discussed in the introduction to this section
EXAMPLE 1 The state table shown in Table 2 describes a finite -state
machine with S = {s 0,s1,s2,s3}, I = {0, 1}, and O = {0, 1} .T h ev a l u e so f
the transition function f are displayed in the first two columns, and the
values of the output function g are displayed in the last two columns.
Another way to represent a finite -state machine is to use a state diagram,
which is a directed graph with labeled edges. In this diagram, each state is
represented by a circle. Arrows labeled with the input and output pair are
shown for each transition.munotes.in

Page 38

38
An input string takes the starting state through a sequence of states,
as determined by the transition function. As we read the input string
symbol by symbol (from left to r ight), each input symbol takes the
machine from one state to another. Because each transition produces an
output, an input string also produces an output string.
Suppose that the input string is x = x 1x2...x k. Then, reading this
input takes the machin e from state s 0to state s 1,w h e r es 1=f( s 0,x1), then
to state s2, where s2 = f (s 1,x2), and so on, with sj = f (s j−1,xj)f o rj=1 ,2 ,
. . . , k, ending at state sk = f (s k−1,xk). This sequence of transitions
produces an output string y 1y2...y k,w h e r ey 1=g ( s 0,x1) is the output
corresponding to the transition from s 0to s 1,y2=g ( s 1,x2) is the output
corresponding to the transition from s 1to s 2, and so on. In general, y j=
g(sj−1,xj) for j = 1, 2, . . . , k. Hence, we can extend the defin ition of the
output function g to input strings so that g(x) = y, where y is the output
corresponding to the input string x. This notation is useful in many
applications.
EXAMPLE 4 Find the output string generated by the finite -state machine
in Figure 3 if the input string is 101011.
Solution: The output obtained is 001000. The successive states and
outputs are shown in Table 4.munotes.in

Page 39

39
6.6 FINITE -STATE AUTOMATA
A finite -state automaton M = (S, I, f, s 0, F ) consists of a finite set S of
states, a finite input alphabet I, a transition function f that assigns a next
state to every pair of state and input (so that f : S × I →S), an initial or
start state s0, and a subset F of S consisting of final (or accepting states).
Example : -A finite -state automaton M = (S, I, f, s 0, F ) consists of a finite
set S of states, a finite inputalphabet I, a transition function f that assigns a
next state to every pair of state and input(so that f : S × I →S), an initial
or start state s0, and a subset F of S consisting of final(or accept ing states).
Regular Expression: -
DEFINITION 1 The regular expressions over a set I are defined
recursively by:
the symbol ∅is a regular expression;
the symbol λ is a regular expression;
the symbol x is a regular expression whenever x ∈I;
the symbols (A B), (A ∪B), and A ∗are regular expressions whenever
Aand B are regular expressions.
Each regular expression represents a set specified by these rules:
∅represents the empty set, that is, the set with no strings;
λ represents the set {λ}, which is the setcontaining the empty string;
x represents the set {x} containing the string with one symbol x;
(AB) represents the concatenation of the sets represented by A and by B;
(A∪B) represents the union of the sets represented by A and by B;munotes.in

Page 40

40A∗represents the Kleene closure of the set represented by A.
Sets represented by regular expressions are called regular sets. Henceforth
regular expressions will be used to describe regular sets, so when we refer
to the regular set A, we will mean the regula r set represented by the
regular expression A. Note that we will leave out outer parentheses from
regular expressions when they are not needed.
EXAMPLE 1 What are the strings in the regular sets specified by the
regular expressions 10 ∗,( 1 0 ) ∗,0∪01,
0(0∪1)∗,a n d( 0 ∗1)∗?
Solution: The regular sets represented by these expressions are given in
Table 1, as the reader should verify
EXAMPLE 2 Find a regular expression that specifies each of these sets:
(a) the set o f bit strings with even length
(b) the set of bit strings ending with a 0 and not containing 11
(c) the set of bit strings containing an odd number of 0s
Solution: (a) To construct a regular expression for the set of bit strings
with even length, we use t he fact that such a string can be obtained by
concatenating zero or more strings each consisting of two bits. The set of
strings of two bits is specified by the regular expression (00 ∪01∪10
∪11). Consequently, the set of strings with even length is speci fied by (00
∪01∪10∪11)* .
(b) A bit string ending with a 0 and not containing 11 must be the
concatenation of one or more strings where each string is either a 0 or a
10. (To see this, note that such a bit string must consist of 0 bits or 1 bits
each fo llowed by a 0; the string cannot end with a single 1 because we
know it ends with a 0.) It follows that the regular expression (0 ∪10)∗(0
∪10) specifies the set of bit strings that do not contain 11 and end with a
0. [Note that the set specified by (0 ∪10)∗includes the empty string,
which is not in this set, because the empty string does not end with a 0.]
(c) A bit string containing an odd number of 0s must contain at least one 0,
which tells us that it starts with zero or more 1s, followed by a 0, foll owed
by zero or more 1s. That is, each such bit string begins with a string of the
form 1j 01k for nonnegative integersj and k. Because the bit stringmunotes.in

Page 41

41contains an odd number of 0s, additional bits after this initial block can be
split into blocks each star ting with a 0 and containing one more 0. Each
such block is of the form 01p01q, where p and q are nonnegative integers.
Consequently, the regular expression 1 ∗01∗(01∗01∗)∗specifies the set of
bit strings with an odd number of 0s.
6.7 REG ULAR SETS AND REGU LAR GRAMMARS
In Section 13.1 we introduced phrase -structure grammars and defined
different types of grammars. In particular we defined regular, or type 3,
grammars, which are grammars of the form G=(V, T , S, P ) ,w h e r ee a c h
production is of the form S→λ,A→a,o rA→aB,w h e r e ais a terminal
symbol, and Aand Bare nonterminal symbols. As the terminology
suggests, there is a close connection between regular grammars and
regular sets.
THEOREM 1 A set is generated by a regular grammar if and only if it is a
regular set.
Proof: First we show that a set generated by a regular grammar is a
regular set. Suppose that G=(V, T , S, P ) is a regular grammar generating
the set L(G) .To show that L(G) is regular we will build a nondeterministic
finite -state machine M=(S, I, f, s 0,F) that recognizes L(G) .
LetS, the set of states, contain a state sAfor each no terminal symbol Aof
Gand an additional state sF, which is a final state. The start state s0 is the
state formed f rom the start symbol S. The transitions of Mare formed from
the productions of Gin the following way. A transition from sAtosFon
input of ais included if A→ais a production, and a transition from sAto
sBon input of ais included if A→aBis a production. The set of final states
includes sFand also includes s0 ifS→λ is a production in G.I ti sn o th a r d
to show that the language recognized by Mequals the language generated
by the grammar G, that is, L(M) =L(G) . This can be done by deter mining
the words that lead to a final state. The details are left as an exercise for
the reader.munotes.in

Page 42

42
6.8 TURING MACHINE
There are other machines called linear bounded automata ,m o r e
powerful than pushdown automata, that can recognize sets such as
{0n1n2n|n=0,1,2,... }. In particular, linear bounded automata can
recognize context -sensitive languages. However, these machines cannot
recognize all the languages generated b yp h r a s e -structure grammars. To
avoid the limitations of special types of machines, the model known as a
Turing machine , named after the British mathematician Alan Turing, is
used. A Turing machine is made up of everything included in a finite -state
machin e together with a tape, which is infinite in both directions. A Turingmunotes.in

Page 43

43machine has read and write capabilities on the tape, and it can move back
and forth along this tape. Turing machines can recognize all languages
generated by phrase -structure grammars. In addition, Turing machines can
model all the computations that can be performed on a computing
machine. Because of their power, Turing machines are extensively studied
in theoretical computer science.
DEFINITION 1 A Turing machine T = (S, I, f, s 0)c o n s ists of a finite set S
of states, an alphabet I containingthe blank symbol B, a partial function f
from S × I to S × I × {R, L}, and a starting state s 0
To interpret this definition in terms of a machine, consider a control unit
and a tape divided into ce lls, infinite in both directions, having only a
finite number of nonblank symbols on it at any given time, as pictured in
Figure 1. The action of the Turing machine at each step of its operation
depends on the value of the partial function ffor the curren t state and tape
symbol.
At each step, the control unit reads the current tape symbol x. If the control
unit is in state sand if the partial function fis defined for the pair (s, x)
with f( s ,x ) =(s, x, d) , the control unit
1. enters the state s’,
2. writes the symbol xin the current cell, erasing x,a n d
3. moves right one cell if d=Ror moves left one cell if d=L.
We write this step as the five -tuple (s, x, s ’,x’,d ). If the partial function f
is undefined for the pair (s, x) , then the Turin g machine Twill halt.
A common way to define a Turing machine is to specify a set of five -
tuples of the form (s, x, s ’,x’,d ). The set of states and input alphabet is
implicitly defined when such a definition is used.
At the beginning of its operation a Turing machine is assumed to be in the
initial state s0and to be positioned over the leftmost nonblank symbol on
the tape. If the tape is all blank, the control head can be positioned over
any cell. We will call the positioning of the control head over t he leftmost
nonblank tape symbol the initial position of the machine.
EXAMPLE 1 What is the final tape when the Turing machine Tdefined
by the seven fivetuples (s0,0,s0,0,R ),(s0,1,s1,1,R ),(s0,B ,s 3,B ,R ) ,
(s1,0,s0,0,R ),(s1,1,s2,0,L )
(s1,B ,s 3,B ,R ) ,a n d (s2,1,s3,0,R )is run on the tape shown in Figure
2(a)?munotes.in

Page 44

44
Solution: We start the operation with Tin state s0 and with Tpositioned
over the leftmost nonblank symbol on the tape. The first step, using the
five-tuple (s0,0,s0,0,R ), reads the 0 in the leftmost nonblank cell, stays
in state s0, writes a 0 in this cell, and moves one cell right.
The second step, using the fi ve-tuple (s0,1,s1,1,R ), reads the 1 in the
current cell, enters state s1, writes a 1 in this cell, and moves one cell
right. The third step, using the five -tuple (s1,0,s0,0,R ), reads the 0 in the
current cell, enters state s0, writes a 0 in this ce ll, and moves one cell
right. The fourth step, using the five -tuple (s0,1,s1,1,R ), reads the 1 in
the current cell, enters state s1, writes a 1 in this cell, and moves right one
cell. The fifth step, using the five -tuple (s1,1,s2,0,L ),r e a d st h e1 in the
current cell, enters state s2, writes a 0 in this cell, and moves left one cell.munotes.in

Page 45

45The sixth step, using the five -tuple (s2,1,s3,0,R ),r e a d st h e1i nt h e
current cell, enters the state s3, writes a 0 in this cell, and moves right one
cell. Finally, in the seventh step, the machine halts because there is no
five-tuple beginning with the pair (s3,0)inthe description of the machine.
6.9 GODEL NUMBERS:
In mathematical logic, a Gödel num bering is a function that assigns
to each symbol and well -formed formula of some formal language a
unique natural number, called its Gödel number. The concept was used by
Kurt Gödel for the proof of his incompleteness theorems. (Gödel 1931)
AG ö d e ln u m b e ring can be interpreted as an encoding in which a
number is assigned to each symbol of a mathematical notation, after which
a sequence of natural numbers can then represent a sequence of symbols.
These sequences of natural numbers can again be represented by single
natural numbers, facilitating their manipulation in formal theories of
arithmetic.
Gödel noted that statements within a system can be represented by
natural numbers. The significance of this was that properties of statements
–such as their tru th and falsehood –would be equivalent to determining
whether their Gödel numbers had certain properties. The numbers
involved might be very long indeed (in terms of number of digits), but this
is not a barrier; all that matters is that we can show such nu mbers can be
constructed.
In simple terms, we devise a method by which every formula or
statement that can be formulated in our system gets a unique number, in
such a way that we can mechanical ly convert back and forth between
formulas and Gödel numbers. Clearly there are many ways this can be
done. Given any statement, the number it is converted to is known as its
Gödel number. A simple example is the way in which English is stored as
as e q u e n c e of numbers in computers using ASCII or Unicode:
The word HELLO is represented by (72,69,76,76,79) using decimal
ASCII.
The logical formula x=y => y=x is represented by
(120,61,121,32,61,62,32,121,61,120) using decimal ASCII.
6.10 SUMMARY
Here, we in troduced the concept of a Turing machine. We have
shown how Turing machines can be used to recognize sets.munotes.in

Page 46

466.11 EXERCISE
1.Construct a deterministic finite -state automaton that recognizes the set
of all bit strings beginning with 01.
2.Const ruct a deterministic finite -state automaton that recognizes the set
of all bit strings that end with 10.
3.Construct a deterministic finite -state automaton thatrecognizes the set
of all bit strings that contain thestring 101.
4.Construct a deterministic f inite-state automaton that recognizes the set
of all bit strings that do not contain threeconsecutive 0s.
5.Construct a deterministic finite -state automaton that recognizes the set
of all bit strings that contain exactlythree 0s.
6.Construct a deterministic fi nite-state automaton that recognizes the set
of all bit strings that contain at leastthree 0s.
7.Construct a deterministic finite -state automaton that recognizes the set
of all bit strings that contain three consecutive 1s.
8.Construct a deterministic finite -state automaton that recognizes the set
of all bit strings that begin with 0 orwith 11.
9.Construct a deterministic finite -state automaton that recognizes the set
of all bit strings that begin and end with 11.
10.Construct a deterministic finite -state automaton that recognizes the set
of all bit strings that contain an even number of 1s.
11.Construct a deterministic finite -state automaton that recognizes the set
of all bit strings that contain an odd numberof 0s.
6.12 REFERENCES
1.Discrete Mathematics and Its Applic ations, Seventh Edition by
Kenneth H. Rosen, McGraw Hill Education (India) Private Limited.
(2011)
2.Norman L. Biggs, Discrete Mathematics, Revised Edition, Clarendon
Press, Oxford 1989.
3.Data Structures Seymour Lipschutz, Schaum’s out lines, McGraw -
Hill Inc .
4.Elements of Discrete Mathematics: C.L. Liu , Tata McGraw -Hill
Edition .
5.Concrete Mathematics (Foundation for Computer Science): Graham,
Knuth, Patashnik Second Edition, Pearson Education.
6.Discrete Mathematics: SemyourLipschutz, Marc Lipson, Schaum’s out
lines, McGraw -Hill Inc.
7.Foundations in Discrete Mathematics: K.D. Joshi, New Age
Publication, New Delhi.
munotes.in

Page 47

47Unit -III
7
GRAPHS
Unit Structure
7.0 Objective
7.1 Definition
7.2 Adjacency matrix
7.3 path matrix
7.4 Representing relations using diagraphs
7.5 Warshall’s algorithm -shortest path
7.6 Linked representation of a graph
7.7 Operations on graph with algorithms
7.8 Traversing a graph -
7.8.1 Breadth -First search and
7.8.2 Depth -First search.
7.0 OBJECTIVE
●This chapter will cover these topics like Graphs, directed graphs ,
operations on graphs , finding shortest paths which appear in many
areas of mathematics and computer science.
●Graphs are discrete structures consisting of vertices and edges that
connect these vertices. There are different kinds of graphs, depending
on whether edges have directions, whether multiple edges can connect
the same pair of vertices, and whether loops are allowed.
●We will describe how graphs can be used to model acquaintanceship s
between people, collaboration between researchers, telephone calls
between telephone numbers, and links between websites.
●We will show how graphs can be used to model roadmaps and the
assignment of jobs to employees of an organization.
●Graphs can be us ed to determine whether a circuit can be implemented
on a planar circuit board.
●We can determine whether two computers are connected by a
communications link using graph models of computer networks.
●Graphs with weights assigned to their edges can be used to solve
problems such as finding the shortest path between two cities in a
transportation network.munotes.in

Page 48

48●We can also use graphs to schedule exams and assign channels to
television stations.
●This chapter will introduce the basic concepts of graph theory and
present many different graph models.
●To solve the wide variety of problems that can be studied using
graphs, we will introduce many different graph algorithms. We will
also study the complexity of these algorithms.
7.1 DEFINITION AND ELEMENTARY RESULTS:
The definition of a graph:
Graph:
A graph G = (V , E) consists of V , a nonempty set of vertices also called
nodesand E, a set of edges. Each edge has either one or two vertices
associated with it, called its endpoints.
By definition we can say:
●Ag raph G consists of two things:
(i) A set V = V (G) whose elements are called vertices, points, or
nodes of G.
(ii) A set E = E(G) of unordered pairs of distinct vertices called
edges of G.
●Vertices u and v are said to be adjacent or neighbors if there is an
edge e = {u, v}.
In this case, u and v are called the endpoints of e, and e is
said to connect u and v.
Also, the edge e is said to be incident on each of its
endpoints u and v.
●Symbolically, each vertex v in V is represented by a dot (or small
circle), and each edge e = {v1, v2} is represented by a curve which
connects its endpoints v1 and v2
●For example, following Figure 1 represents the graph G(V,E)
where:
Figure 1munotes.in

Page 49

49(i) V consists of vertices A, B, C, D.
(ii) E consists of edges as follows:
e1 = {A,B}, e2 = {B,C}, e3 = {C,D}, e4 = {A,C}, e5 = {B,D}.
The definition A directed graph (or digraph):
A directed graph (or digraph):
A directed graph (or also called as digraph) (V, E) consists of a nonem pty set of
vertices V and a set of directed edges (or arcs) E.
Each directed edge is associated with an ordered pair of vertices.
The directed edge associated with the ordered pair (u, v) is said to start at vertex u
and end at vertex v.
uv
Figure 2
For example graph given in figure 2 is a digraph. There is a directed edge
from vertex 0 to vertex 1 , but no directed edge from vertex 1 to vertex 0
Graph Theory common terminology :
●Anarcis a directed line (a pair of ordered vertices).
●Anedge is line joining a pair of nodes.
○Incident edges are edges which share a vertex. A edge and vertex are
incident if the edge connects the vertex to another.
●Aloop is an edge or arc that joins a vertex to itself.
○Adjacent vertices are vertices which are con nected by an edge.
○Thedegree of a vertex is simply the number of edges that connect to
that vertexor is the number of edges with v as an end vertex.munotes.in

Page 50

50○Thedegree of the vertex v, is denoted as d(v) .
○By convention, we count a loop twice and parallel edges
contribute separately.
○A pendant vertex is a vertex whose degree is 1.
○Anisolated vertex is a vertex whose degree is 0.
○Apredecessor is the node (vertex) before a given vertex on a path.
○Asuccessor is the node (vertex) following a given vertex on a path.
●Aw a l k is a series of vertices and edges.
○Acircuit is a closed walk with every edge distinct.
○Aclosed walk is a walk from a vertex back to itself; a series of
vertices and edges which begins and ends at the same place.
○Acycle is a closed walk with no re peated vertices (except that the first
and last vertices are the same).
○Apath is a walk where no repeated vertices. A u-vpath is a path
beginning at u and ending at v.
○Au-vw a l k would be a walk beginning at u and ending at v.
Types of Graphs Definition
Undirected
GraphAn undirected graph is one in which edges have
no orientation.
Simple Graph A graph is simple if it has no parallel edges or
loops.
The given graph is not simple.
Empty Graph A graph with no edges (i.e. E is empty) is empty.
Null Graph A graph with no vertices (i.e. V and E are empty)
is a null graph.
Trivial Graph A graph with only one vertex is trivial.
Complete Graph A simple graph is called a complete graph if each
pair of distinct vertices is joined by an edge
Weighted Graph A graph is a weighted graph if a number (weight)
is assigned to each edge.
Such weights might represent,
for example, costs, lengths or cap acities, etc.
depending on the problem at hand .
These graph are also called as a networkmunotes.in

Page 51

51Isomorphic
GraphTwo graphs are said to be isomorphic if there is
one to one correspondence between their vertices
and their edges such that incidences are pr eserved
Properties preserved by isomorphism of graphs.
• must have the same number of vertices
• must have the same number of edges
• must have the same number of vertices with
degree k
•for every proper subgraph g of one graph, there
must be a proper subgraph of the other graph that
is isomorphic of g
Parallel Edges In a graph, if a pair of vertices is connected by
more than one edge, then those edges are called
parallel edges.
Multi Graph A graph having parallel edges is known as a
Multigraph.
Connected
GraphA graph G is said to be connected if there exists a
path between every pair of vertices.
There should be at least one edge for every vertex
in the graph.
So that we can say that it is connected to some
other vertex at the other side of the edge.
Disconnected
GraphA graph G is disconnected, if it does not contain at
least two connected vertices.
7.2 ADJACENCY MATRIX
One way to represent a graph without multiple edges is to list all
the edges of this graph. Another way to represent a graph with no multiple
edges is to use adjacency lists, which specify the vertices that are adjacent
to each vertex of the graph.
Use adjacency lists to describe the simple graph given in Figure 3:
Figure 3munotes.in

Page 52

52An Adjacency List for a Simple Graph.
Vertex Adjacent Vertices
a b, c, e
b A
c a, d, e
d c, e
e a, c, d
Represent the directed graph shown below Figure 4 by listing all
the vertices that are the terminal vertices of edges starting at each vertex of
the graph.
Figure 4
An Adjacency List for a Directed Graph.
Initial Vertex Terminal Vertices
a b, c, d, e
b b, d
c a, c, e
d -
e b, c, d
To simplify computation, graphs can be represented using
matrices.
An adjacency matrix is a way of representing a graph as a matrix
of booleans (0's and 1's).
A finite graph can be represented in the form of a square matrix on
a computer, where the boolean value of the matrix indicates if there is a
direct path between two vertices.munotes.in

Page 53

53Definition:
Suppose that G = (V , E) is a simple graph with n vertices i. e| V| =n .
Suppose that the vertices of G are listed arbitrarily as v1, v2,..., vn. The
adjacency matrix A (or AG) of G, with respect to this listing of the
vertices, is the n x n zero –one matrix with 1 as its (i, j )th entry when vi
and vj are adjacent, and 0 as its (i, j )th entry when they are not adjacent.
In other words, if its adjacency matrix is A = [a ij], then
For example, we have a graph below, Use an adjacency matrix to
represent the graph .
Figure 5
Solution:
Things to remember:
●The adjacency matrix of a simple graph is symmetric , that is,a ij=
aji, because both of these entries are 1 when vi an d vj are adjacent, and
both are 0 otherwise. Furthermore, because a simple graph has no
loops, each entry aii, i = 1, 2, 3,...,n, is 0 .
●Adjacency matrices can also be used to represent undirected
graphs with loops and with multiple edges. A loop at the ve rtex vi is
represented by a 1 at the (i, i)th position of the adjacency matrix.
When multiple edges connecting the same pair of vertices vi and vj , or
multiple loops at the same vertex, are present, the adjacency matrix is
no longer a zero –one matrix, bec ause the (i, j )th entry of this matrix
equals the number of edges that are associated to {vi, vj }.
●All undirected graphs, including multigraphs and pseudographs, have
symmetric adjacency matrices.munotes.in

Page 54

54●Example: Adjacency matrix for given graph is :
Figure 6
Pros of Adjacency Matrix
●The basic operations like adding an edge, removing an edge, and
checking whether there is an edge from vertex i to vertex j are
extremely time efficient, constant time operations.
●If the graph is dense and the number of edges is large, an adjacency
matrix should be the first choice. Even if the graph and the adjacency
matrix is sparse, we can represent it using data structures for sparse
matrices.
●The biggest advantage, however, comes from the use of matrices. The
recent advances in hardware enable us to perform even expensive
matrix operations on the GPU.
●By performing operations on the adjacent matrix, we can get important
insights into the nature of the graph and the relationship between its
vertices.
Cons of Adjacency Matrix
●The VxV space requirement of the adjac ency matrix makes it to
occupy lot of memory space. Graphs out in the wild usually don't have
too many connections and this is the major reason why adjacency lists
are the better choice for most tasks.
●While basic operations are easy, operations like in Ed ges and out
Edges are expensive when using the adjacency matrix representation.
7.3 PATH MATRIX
First we will see the definition:
Definition:
Let G be a graph with m edges, and u and v be any two vertices in G. The
path matrix for vertices u and v denot ed by P(u, v) = [p ij]q×m, where q is
the number of different paths between u and v.munotes.in

Page 55

55In other word,
Clearl y, a path matrix is defined for a particular pair of vertices, the rows
in P(u, v) correspond to different paths between u and v, and the columns
correspond to different edges in G.
For example, consider the graph in following Figure:
The different paths between the vertices v3 and v4 are
p1 = {e8, e5},
p2 = {e8, e7, e3} and
p3 = {e8, e6, e4, e3}.
The path matrix for v3, v4 is given by
Things to remember about the path matrix.
1. A column of all zeros corresponds to an edge that does not lie in any
path between u and v. 2. A column of all ones corresponds to an edge
that lies in every path between u and v.
3. There is no row with all zeros.
4. The ring sum of any two rows in P(u, v) corresponds to a cycle or an
edge -disjoint union of cycles
7.4 REPRESENTING RELATIONS USING DIAGRAPHS
●In this section we will give a brief explanation of procedures for
graphing a relation (done in UNIT I).
●Agraph is nothing more than an illustration that gives us, at a glance, a
clearer idea of the situation under consideration.
●A road map indicates where we have been and how to proceed to reach
our destination.
●A flow chart helps us to zero in on the proced ures to be followed to
code a problem and/or organize the flow of information.munotes.in

Page 56

56●Example:
Let A={0,1,2,3} and let relation R be define on A as :
R={ ( 0 , 0 ) , ( 0 , 3 ) , ( 1 , 2 ) , ( 2 , 1 ) , ( 3 , 2 ) , ( 2 , 0 ) }
The elements of A are called the vertices of the graph and are
represe nted by labelled points or occasionally by small circles.
Connect vertex a to vertex b with an arrow, called an edge of the
graph, going from vertex a to vertex b if and only if a R b.
This type of graph of a relation r is called a directed graph or digr aph.
The result is:
Figure 7
Relations are represented using ordered pairs, matrix and digraphs:
Ordered Pairs –
●In this set of ordered pairs of x and y are used to represent relation.
In this corresponding values of x and y are represented using
parenthesis.
●Example: {(1, 1), (2, 4), (3, 9), (4, 16), (5, 25)}
Representing using Matrix –
●In this zero -one is used to represent the relationship that exists
between two sets.
●In this if a eleme nt is present then it is represented by 1 else it is
represented by 0.
●In this method it is easy to judge if a relation is reflexive,
symmetric or transitive just by looking at the matrix.munotes.in

Page 57

57●Example:
Let P = {1, 2, 3, 4}, Q = {a, b, c, d}
and R = {(1, a), (1, b), (1, c), (2, b), (2, c), (2, d)}.
The matrix of relation R is shown as fig:
Digraph –
●A digraph is known was directed graph. It consists of set ‘V’ of
vertices and with the edges ‘E’.
●Here E is represented by ordered pair of Vertices.
●In the edge (a, b), a is the initial vertex and b is the final vertex.
●If edge is (a, a) then this is regarded as loop.
●Example: Suppose we have relation forming
R={ ( 1 ,2 ) ,( 1 ,3 ) ,( 1 ,4 ) ,( 2 ,3 ) ,( 2 ,4 ) ,( 3 ,4 ) }
This relation is represented using digraph as:
Figure 8
7.5 WARSHALL’S ALGORITHM -SHORTEST PATH
●The Floyd Warshall Algorithm is for solving the All Pairs Shortest
Path problem.
●The problem is to find shortest distances between every pair of
vertices in a given edge weighted directed Graph.munotes.in

Page 58

58●We initialize the solution matrix same as the input graph matrix as a
first step.
●Then we update the solution matrix by considering all vert ices as an
intermediate vertex.
●The idea is to one by one pick all vertices and updates all shortest
paths which include the picked vertex as an intermediate vertex in the
shortest path.
●When we pick vertex number k as an intermediate vertex, we already
have considered vertices {0, 1, 2, .. k -1} as intermediate vertices.
●For every pair (i, j) of the source and destination vertices respectively,
there are two possible cases.
1)k is not an intermediate vertex in shortest path from i to j.
We keep the value of dist[i][j] as it is.
2)k is an intermediate vertex in shortest path from i to j.
We update the value of
dist[i][j] as dist[i][k] + dist[k][j] if dist[i][j] > dist[i][k] + dist[k][j]
Floyd Warshall Algorithm Complexity
●Time Complexity
There are three loops. Each loop has constant complexities. So, the
time complexity of the Floyd -Warshall algorithm is O(n3).
●Space Complexity
The space complexity of the Floyd -Warshall algorithm is O(n2).
Floyd Warshall Algorithm Applications
●To find the shortest path is a directed graph
●To find the transitive closure of directed graphs
●To find the Inversion of real matrices
●For testing whether an undirected graph is bipartitemunotes.in

Page 59

59Example:
Let the given graph be:
Figure 9
Solution:
Follow the steps below to find the shortest path between all the
pairs of vertices.
1.Create a matrix A0of dimension n*n=n2where n is the number of
vertices.
The row and the column are indexed as i and j respectively. i and j
are the vertices of the graph.
Each cell A[i][j] is filled with the distance from the ith vertex to the jth
vertex.
If there is no path from ithvertex to jthvertex, the cell is left as infinity.
2.Now, crea te a matrix A1 using matrix A0. The elements in the first
column and the first row are left as they are. The remaining cells are
filled in the following way.
Let k be the intermediate vertex in the shortest path from source to
destination. In this step, k is the first vertex. A[i][j] is filled with (A[i][k] +
A[k][j]) if (A[i][j] > A[i][k] + A[k][j]).
That is, if the direct distance from the source to the destination is
greater than the path through the vertex k, then the cell is filled with
A[i][k] + A[k ][j].
In this step, k is vertex 1. We calculate the distance from source
vertex to destination vertex through this vertex k.munotes.in

Page 60

60
For example: For A1[2, 4], the direct distance from vertex 2 to 4 is 4
and the sum of the distance from vertex 2 to 4 through vertex (ie. from
vertex 2 to 1 and from vertex 1 to 4) is 7. Since 4 < 7, A0[2, 4] is filled
with 4.
3.Similarly, A2is created using A1. The elements in the second column
and the second row are left as they are.
Inthis step, k is the second vertex (i.e. vertex 2). The remaining
steps are the same as in step 2.
4.Similarly, A3 and A4 is also created.
5.A4 gives the shortest path between each pair of vertices.munotes.in

Page 61

617.6 LINKED REPRESENTATION OF A GRAPH:
In the linked representation, an adjacency list is used to store the
Graph into the computer's memory.
Consider the undirected graph shown in the following figure and
check the adjacency list representation.
An adjacency list is maintained for each node present in the graph
which stores the node value and a pointer to the next adjacent node to the
respective node.
If all the adjacent nodes are traversed then store the NULL in the
pointer field of last node of the list.
The sum of the lengths of adjacency lists is equal to twice of the
number of edges present in a nu n d i r e c t e dg r a p h .
Consider the directed graph shown in the following figure and
check the adjacency list representation of the graph.
In a directed graph, the sum of lengths of all the adjacency lists is
equal to the number of edges present in the graph.
In the case of weighted directed graph, each node contains an extra
field that is called the weight of the node. The adjacency list
representation of a directed graph is shown in the following figure.munotes.in

Page 62

62
7.7 OPERATIONS ON GRAPH WITH ALGORITHMS -
The idea is to represent the graph as a list of linked lists where the
head of the linked list is the vertex and all the connected linked lists are
the vertices to whi ch it is connected.
Adding a Vertex in the Graph:
To add a vertex in the graph, the adjacency list can be iterated to
the place where the insertion is required and the new node can be created
using linked list implementation.
For example,
if 5 needs t o be added between vertex 2 and vertex 3 such that vertex 3
points to vertex 5 and vertex 5 points to vertex 2,
then a new edge is created between vertex 5 and vertex 3 and a new edge
is created from vertex 5 and vertex 2.
After adding the vertex, the ad jacency list changes to:
Removing a Vertex in the Graph:
To delete a vertex in the graph, iterate through the list of each
vertex if an edge is present or not.munotes.in

Page 63

63If the edge is present, then delete the vertex in the same way as
delete is performed in a linked list.
For example, the adjacency list translates to the below list if vertex
4 is deleted from the list:
7.8 TRAVERSING A GRAPH:
In this section we discuss two important graph algorithms which
systematically examine the vertices and edges of a graph G.
One is called a depth -first search (DFS) and the other is called a
breadth -first search (BFS). Any partic ular graph algorithm may depend on
the way G is maintained in memory. Here we assume G is maintained in
memory by its adjacency structure.
Our test graph G with its adjacency structure appears in given Fig.
where we assume the vertices are ordered alphab etically.
Figure 10munotes.in

Page 64

64During the execution of our algorithms, each vertex (node) N of G
will be in one of three states, called the status of N, as follows:
STATUS = 1: (Ready state) The initial state of the vertex N.
STATUS = 2: (Waiting state) The vertex N is on a (waiting) list,
waiting to be processed.
STATUS = 3: (Processed state) The vertex N has been processed.
The waiting list for the depth -first search (DFS) will be a
(modified) STACK (which we write horizo ntally with the top of STACK
on the left), whereas the waiting list for the breadth -first search (BFS) will
be a QUEUE.
Depth -first Search:
●The general idea behind a depth -first search beginning at a starting
vertex A is as follows. First we process the starting vertex A. Then we
process each vertex N along a path P which begins at A; that is, we
process a neighbor of A, then a neighbor of A, and so on.
●After coming to a “dead end,” that is to a vertex with no unprocessed
neighbor, we backtrack on the path P until we can continue along
another path P.
●And so on.
●The backtracking is accomplished by using a STACK to hold the
initial vertices o f future possible paths.
●We also need a field STATUS which tells us the current status of any
vertex so that no vertex is processed more than once.
●The depth -first search (DFS) algorithm appears in Fig. 8 -31.
●The algorithm will process only those vertices which are connected to
the starting vertex A, that is, the connected component including A.
●Suppose one wants to process all the vertices in the graph G. Then the
algorithm must be modified so that it begins again with another vertex
(which we call B) th at is still in the ready state (STATE = 1).
●This vertex B can be obtained by traversing through the list of vertices.
●Depth first search (DFS) algorithm starts with the initial node of the
graph G, and then goes to deeper and deeper until we find the goal
node or the node which has no children.
●The algorithm, then backtracks from the dead end towards the most
recent node that is yet to be completely unexplored.
●The data structure which is being used in DFS is stack.
●The process is similar to BFS algorith m.
●In DFS, the edges that leads to an unvisited node are called discovery
edges while the edges that leads to an already visited node are called
block edges.munotes.in

Page 65

65Algorithm
Step 1: SET STATUS = 1 (ready state) for each node in G
Step 2: Push the starting node A on the stack and set its STATUS = 2
(waiting state)
Step 3: Repeat Steps 4 and 5 until STACK is empty
Step 4: Pop the top node N. Process it and set its STATUS = 3 (processed
state)
Step 5: Push on the stack all the neighbours of N that are in the ready state
(whose STATUS = 1) and set their
STATUS = 2 (waiting state)
[END OF LOOP]
Step 6: EXIT
Example :
Consider the graph G along with its adjacency list, given in the
figure below. Calculate the order to print all the nodes of the graph starting
from node H, by using depth first search (DFS) algorithm.
Figure 11
Solution :
Push H onto the stack
STACK : H
POP the top element of the stack i.e. H, print it and push all the neighbours
of H onto the stack that are is ready state.
Print H
STACK : A
Pop the top element of the stack i.e. A, print it and push all the neighbours
of A onto the stack that are in ready state.
Print A
Stack : B, D
Pop the top element of the stack i.e. D, print it and push al l the neighbours
of D onto the stack that are in ready state.munotes.in

Page 66

66Print D
Stack : B, F
Pop the top element of the stack i.e. F, print it and push all the neighbours
of F onto the stack that are in ready state.
Print F
Stack : B
Pop the top of the stack i.e. B and push all the neighbours
Print B
Stack : C
Pop the top of the stack i.e. C and push all the neighbours.
Print C
Stack : E, G
Pop the top of the stack i.e. G and push all its neighbours.
Print G
Stack : E
Pop the top of the stack i.e. E and push all its neighbours.
Print E
Stack :
Hence, the stack now becomes empty and all the nodes of the graph have
been traversed.
The printing sequence of the graph will be :
H→A→D→F→B→C→G→E
Breadth -First search:
●The general idea behind a breadth -first search beginning at a starting
vertex A is as follows. First we process the starting vertex A.
●Then we process all the neighbors of A.
●Then we process all the neighbors of neighbors of A. And so on.
●Naturally we need to keep track of the neighbors of a vertex, and we
need to guarantee that
●no vertex is processed twice.
●This is accomplished by using a QUEUE to hold vertices that are
waiting to be processed, and by a field STATUS which tells us the
current status of a vertex.
●The breadth -first search (BFS) algorithm appears in Fig. 8 -33, Again
the algorithm will process only those vertices which are connected to
the starting vertex A, that is, the connected component including A.munotes.in

Page 67

67●Suppose one wa nts to process all the vertices in the graph G. Then the
algorithm must be modified so that it begins again with another vertex
(which we call B) that is still in the ready state (STATUS = 1).
●This vertex B can be obtained by traversing through the list o f vertices.
●Breadth first search is a graph traversal algorithm that starts traversing
the graph from root node and explores all the neighbouring nodes.
●Then, it selects the nearest node and explore all the unexplored nodes.
●The algorithm follows the sam e process for each of the nearest node
until it finds the goal.
●The algorithm of breadth first search is given below.
●The algorithm starts with examining the node A and all of its
neighbours.
●In the next step, the neighbours of the nearest node of A are explored
and process continues in the further steps.
●The algorithm explores all neighbours of all the nodes and ensures that
each node is visited exactly once and no node is visited twice.
Algorithm
Step 1: SET STATUS = 1 (ready state)
for each node in G
Step 2: Enqueue the starting node A
and set its STATUS = 2
(waiting state)
Step 3: Repeat Steps 4 and 5 until
QUEUE is empty
Step 4: Dequeue a node N. Process it
and set its STATUS = 3
(processed state).
Step 5: Enqueue all the neighbours of
Nt h a t are in the ready state
(whose STATUS = 1) and set
their STATUS = 2
(waiting state)
[END OF LOOP]
Step 6: EXIT
Example
Consider the graph G shown in the following image, calculate the
minimum path p from node A to node E. Given that each edge has a lengt h
of 1.munotes.in

Page 68

68
Solution:
Minimum Path P can be found by applying breadth first search
algorithm that will begin at node A and will end at E. the algorithm uses
two queues, namely QUEUE1 and QUEUE2. QUEUE1 holds all the
nodes that are to be processed while QUEUE2 holds all the node s that are
processed and deleted from QUEUE1.
Lets start examining the graph from Node A.
1. Add A to QUEUE1 and NULL to QUEUE2.
QUEUE1 = {A}
QUEUE2 = {NULL}
2. Delete the Node A from QUEUE1 and insert all its neighbours. Insert
Node A into QUEUE2
QUEUE1 = {B, D}
QUEUE2 = {A}
3. Delete the node B from QUEUE1 and insert all its neighbours. Insert
node B into QUEUE2.
QUEUE1 = {D, C, F}
QUEUE2 = {A, B}
4. Delete the node D from QUEUE1 and insert all its neighbours. Since F
is the only neighbo ur of it which has been inserted, we will not insert it
again. Insert node D into QUEUE2.
QUEUE1 = {C, F}
QUEUE2 = { A, B, D}
5. Delete the node C from QUEUE1 and insert all its neighbours. Add
node C to QUEUE2.
QUEUE1 = {F, E, G}
QUEUE2 = {A, B, D ,C }
6. Remove F from QUEUE1 and add all its neighbours. Since all of its
neighbours has already been added, we will not add them again. Add node
F to QUEUE2.
QUEUE1 = {E, G}
QUEUE2 = {A, B, D, C, F}munotes.in

Page 69

697. Remove E from QUEUE1, all of E's neighbours has already been added
to QUEUE1 therefore we will not add them again. All the nodes are
visited and the target node i.e. E is encountered into QUEUE2.
QUEUE1 = {G}
QUEUE2 = {A, B, D, C, F, E}
Now, backtrack from E to A, using the nodes available in QUEUE2.
The minimum path will be A →B→C→E.
7.9 EXERCISE
Solve the following:
1.Represent the given graph using an adjacency matrix
2.draw an undirected graph represented by the given adjacency matrix
and fi nd the degree of each of its vertex.
3.Solve using BFS and DFS both on given graph:
4.Define incidence, adjacent and degree
5.Define Isolated and pendent vertex , null graph with help of example.
munotes.in

Page 70

708
TREES
Unit Structure
8.0 Objective
8.1 Definition
8.2 Ordered rooted tree
8.3 Binary trees
8.4 Complete and extended binary trees
8.5 Representing binary trees in memory
8.6 Traversing binary trees
8.7 Binary search tree
8.7.1 Algorithms for searching and inserting in binary search trees
8.7.2 Algorithms for deleting in a binary search tree
8.8 Exercise
8.0 OBJECTIVE
In this chapter we are going to learn about:
●the definitions of the following terms: tree, rooted tree; m -ary (and
binary) tree; full m -ary tree.
●Determine its root, if it has one; Given a node in the tree,
determine its parent and all of its children, sib lings, and
descendants, and determine whether the node is a leaf or an
internal vertex; and state whether the tree is m -ary or full m -ary for
some integer m.
●Given a binary tree and a node, find the left and right children of
that node and the left and rig ht subtrees at those children.
●Use trees to model various kinds of networks.
●Use the formulas in the "Properties of Trees" subsection to draw
conclusions about the edges and nodes in a tree.
●Construct a binary search tree for an ordered set of objects and
then use Algorithm 1 to find and add items into the binary search
tree.
●Tree Traversal
●Perform preorder, postorder, and inorder traversals of an ordered
rooted tree.munotes.in

Page 71

718.1 DEFINITION
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 .
Definition of a Tree.
A tree is a connected graph containing no cyc les.
Alternately, a Tree is also called as connected acyclic graph.
A forest is a graph containing no cycles. Note that this means that a
connected forest is a tree.
Tree –terminologies
Node -an object containing a data value and links to other nodes
Edge -directed link, representing relationships between nodes
Root -The start of the tree. The top -most node in the tree Node without
parents is root node. In figure 1 blue node is tree.
Figure 1
Parent (ance stor) -any node with at least one child. The blue nodes in
given figure 2
Figure 2munotes.in

Page 72

72Child (descendant) -any node with a parent , The blue nodes in given
figure 3
Figure 3
Siblings -all nodes on the same level,The blue nodes in given figure 4
Figure 4
Internal node -a node with at least one children (except root) All the
orange nodes as shown in figure 5
Figure 5
External node -a node without children All the orange nodes as shown in
figure 6
Figure 6munotes.in

Page 73

73General Trees
A tree or general trees is defined as a non -empty finite set of elements
called vertices or nodes having the property that each node can have
minimum degree 1 and maximum degree n.
It can be partitioned into n+1 disjoint subsets such that the first subset
contains the root of the tree and remaining n subsets includes the elements
of the n subtree.
Example:
Figure 7
Ordered Trees:
If in a tree at each level, an ordering is defined, then such a tree is
called an ordered tree.
Example:
Figure 8
Properties of Trees
In this section we will discuss about properties of trees; what makes
them special and how they can be used.
●A tree is a connected graph with no cycles.
●There is only one path between each pair of vertices of a tree.
●If a graph G there is one and only one path between each pair of
vertices G is a tree.munotes.in

Page 74

74●A tree T with n vertices has n -1e d g e s .
●A graph is a tree if and only if it a minimal connected.
8.2 ORD ERED ROOTED TREE
●A rooted tree G is a connected acyclic graph with a special node that is
called the root of the tree and every edge directly or indirectly
originates from the root.
●An ordered rooted tree is a rooted tree where the children of each
internal vertex are ordered.
●If every internal vertex of a rooted tree has not more than m children,
it is called an m -ary tree.
●If every internal vertex of a rooted tree has exactly m ch ildren, it is
called a full m -ary tree.
●If m = 2, the rooted tree is called a binary tree.
●An ordered tree is a rooted tree in which the children of each
vertex are assigned a fixed ordering.
Definition:
If a directed tree has exactly one node or vertex called root whose
incoming degree is 0 and all other vertices have incoming degree one,
then the tree is called a rooted tree .
Note: 1. A tree with no nodes is a rooted tree (the empty tree)
2. A single node with no children is a rooted tree.
Figure 9
●Data is often structured like a tree.
●For example, a book has a tree structure: draw a vertex for the
book itself.
Then draw vertices for each chapter, connected to the book vertex.
Under each chapter, draw a vertex for each section, connecting it
to the chapter it belongs to.munotes.in

Page 75

75The graph will not have any cycles; it will be a tree.
But a tree with clear hierarchy which is not present if we don't
identify the book vertex as the “top”.
●As soon as one vertex of a tree is designated as the root, then every
other vertex on the tree can be characterized by its position relative
to the root.
●This works because there is a unique path between any two
vertices in a tree.
●So from any vertex, w e can travel back to the root in exactly one
way.
●This also allows us to describe how distinct vertices in a rooted
tree are related.
●If two vertices are adjacent, then we say one of them is the parent
of the other, which is called the child of the parent .
●Of the two, the parent is the vertex that is closer to the root.
●Thus the root of a tree is a parent, but is not the child of any vertex
(and is unique in this respect: all non -root vertices have exactly
one parent).
●The child of a child of a vertex is called the grandchild of the
vertex (and it is the grandparent).
●More in general, we say that a vertex v is a descendent of a vertex
u provided u is a vertex on the path from v to the root.
●Then we would call u an ancestor of v.
●For most trees (in fac t, all except paths with one end the root),
there will be pairs of vertices neither of which is a descendant of
the other.
●We might call these cousins or siblings .
●In fact, vertices u and v are called siblings provided they have the
same parent.
●In a roo ted tree, the depth or level of a vertex v is its distance from
the root, i.e., the length of the unique path from the root to v. Thus,
the root has depth 0.
●Theheight of a rooted tree is the length of a longest path from the
root (or the greatest depth in the tree).
●Aleafin a rooted tree is any vertex having no children.munotes.in

Page 76

76Example :
For given tree:
Figure 10
We can say,
1.The height of this tree is 3. Also,
2.r, a, b, c, and d are the internal vertices;
3.vertices e, f, g, h, i, and j are the leaves;
4.vertices g, h, and i are siblings;
5.vertex a is an ancestor of j; and
6.j is a descendant of a.
8.3 BINARY TREES
If the out degree of every node is less than or equal to 2, in a
directed tree than the tr ee is called a binary tree.
A tree consisting of the nodes (empty tree) is also a binary tree. A binary
tree is shown in figure 11
Basic Terminology:
●Root: A binary tree has a unique node called the root of the tree.
●Left Child: The node to the left of the root is called its left child.
●Right Child: The node to the right of the root is called its right
child.
Definition:
A binary tree is an ordered 2 -ary tree in which each child is designated
either a left -child or a right -child.munotes.in

Page 77

77Example:
Figure 11
Theleft / right subtree of a vertex v in a binary tree is the binary
subtree spanning the left / right -child of v and all of its descendants.
8.4 COMPLETE AND EXTENDED BINARY TREES
A complete binary tree is a binary tree in which all the levels are
completely filled except possibly the lowest one, which is filled from the
left.
A complete binary tree is just like a full binary tree, but with two
major differences. All the leaf elem ents must lean towards the left.
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 for left as possible.
The depth of the complete binary tree having n nodes is log 2n+1.
Example: The tree shown in figure 12 is a complete binary tree.
Figure 12
●A complete binary tree is just like a full binary tree, but with two
major differences:
○All the leaf elements must lean towards the left.
○The last leaf element might not have a right sibling i.e. a complete
binary tree doesn't have to be a full binary tree.
Creation of Complete Binary Tree:munotes.in

Page 78

78Suppose we have an array of 6 elements shown as belo w:
Full Binary Tree vs. Complete Binary Tree
The above array contains 6 elements, i.e., 1, 2, 3, 4, 5, 6. The following
are the steps to be used to create a complete binary tree:
Step 1: First, we will select th e first element of the array, i.e., 1, and make
a root node of the tree. The number of elements available in the first level
is 1.
Step 2: Now, we will select the second and third elements of the array.
Keep the second element and third element of the arr ay as the left and
right child of the root node respectively shown as below:
As we can observe above, the number of elements available in the second
level is 2.
Step 3: Now, we will select the next two elements f rom the array, i.e., 4
and 5. Keep these two elements on the left and right of node 2 shown as
below:
As we can observe above that nodes 4 and 5 are the left and right child of
node 2 respectively.
Step 4: Now, we will select the last element of the array, i.e., 6, and keep it
as left child of the node 3 as we know that in a complete binary tree, the
nodes are filled from the left side shown as below:munotes.in

Page 79

79
As we can observe that the second level contains 3 elements.
8.5 REPRESENTING BINARY TREES IN MEMORY
Before we start with representation , first let us understand the
following concept:
A binary search tree:
➢A binary search tree is the most common of all the other types of
binary trees.
➢It is a specialized binary tree that comes with properties that are
different and more useful than any other form of a binary tree.
A binary search tree or BST:
➢Just as its name suggests, a binary search tree is used to search data
in the tree.
➢A BST comes with properties that allow it to facilitate efficient
searches.
➢A BST is a binary tree that has the key of the node that is smaller
and greater than nodes in the right su b-tree and nodes in the left
sub-tree respectively.
Now let's start with Representation of binary trees:
1. Linked representation
➢Binary trees in linked representation are stored in the memory as
linked lists.
➢These lists have nodes that aren’ t stored at adjacent or neighboring
memory locations and are linked to each other through the parent -
child relationship associated with trees.
➢In this representation, each node has three different parts –
○pointer that points towards the right node,
○pointer that points towards the left node,
○data element.
➢This is the more common representation.munotes.in

Page 80

80➢All binary trees consist of a root pointer that points in the direction
of the root node.
➢When you see a root node pointing towards null or 0, you should
know that you are dealing with an empty binary tree.
➢The right and left pointers store the address of the right and left
children of the tree.
2. Sequential representation
➢Although it is simpler than linked representation, its inefficiency
makes it a less pr eferred binary tree representation of the two.
➢The inefficiency lies in the amount of space it requires for the
storage of different tree elements.
➢The sequential representation uses an array for the storage of tree
elements.
➢The number of nodes a binary tree has defines the size of the array
being used.
➢The root node of the binary tree lies at the array’s first index.
➢The index at which a particular node is stored will define the
indices at which the right and left children of the node will be
stored.
➢An empty tree has null or 0 as its first index.
Types of binary trees:
Full binary trees:
Full binary trees are those binary trees whose nodes either have
two children or none. In other words, a binary tree becomes a full
binary tree when apart from leaves, all its other nodes have two
children.
Complete binary trees:
Complete binary trees are those that have all their different levels
completely filled. The only exception to this could be their last
level, whose k eys are predominantly on the left.
A binary heap is often taken as an example of a complete binary
tree.
Perfect binary trees:
Perfect binary trees are binary trees whose leaves are present at the
same level and whose internal nodes carry two children.
A common example of a perfect binary tree is an ancestral family
tree.
Pathological degenerate binary trees:
Degenerate trees are those binary trees whose internal nodes have
one child.munotes.in

Page 81

81Their performance levels are similar to linked lists. Learn more
about the types of binary tree.
Benefits of binary trees:
●An ideal way to go with the hierarchical way of storing data
●Reflect structural relationships that exist in the given data set
●Make insertion and deletion faster than linked lists and arrays
●Aflexible way of holding and moving data
●Are used to store as many nodes as possible
●Are faster than linked lists and slower than arrays when comes to
accessing elements
8.6 TRAVERSING BINARY TREE
●Traversing means to visit all the nodes of the tree.
●There are three standard methods to traverse the binary trees.
●These are as follows:
○Preorder Traversal
○Postorder Traversal
○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.
2. Postorder Traversal:
●The postorder traversal of a binary tree is a recursive process.
●The postorder traversal of a tree is
○Traverse t he 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 subtr ee.
○Visit the root of the tree.
○Traverse in inorder the right subtree.munotes.in

Page 82

82Example: Determine the preorder, postorder and inorder traversal of the
binary tree as shown in figure 13
Figure 13
Solution: The preorder, postorder and inorder traversal of the tree is as
follows:
8.7 BINARY SEARCH TREES
Binary search trees have the property that the node to the left contains
a smaller value than the nod e 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: The tree shown in figure14 is a binary search tree.
Figure 14
Algorithm for : 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.munotes.in

Page 83

83The following steps explain a procedure to insert an ITEM in the binary
search tree T.
I.Compare the ITEM with the root node.
II.If ITEM>ROOT NODE, proceed to the right child, and it becomes
a root node for the ri ght subtree.
III.If ITEMIV.Repeat the above steps until we meet a node which has no left and
right subtree.
V.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 shown in figure 15:
Figure 15
Algorithm for Deletion in a Binary Search Tree:
Consider a binary 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.munotes.in

Page 84

841.Deleted Node has no children:
Deleting a node which has no children is very simple, as replace the
node with null.
2.Deleted Node has Only one child:
Replace the value of a deleted node with the only child.
3.Deletion 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 case1
or case2.
Example: Show that t he binary tree shown in fig (viii) after deleting the
root node.
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 shown in figure 16
Figure 16munotes.in

Page 85

858.8 EXERCISE:
Solve the following:
1. Build a binary search tree for the words banana, peach, apple, pear,
coconut, mango, and papaya using alphabetical order.
2. Build a binary search tree for the words oenology, phrenology,
campanology, ornithology, ichthyology, limnology, alchemy, and
astrology using alphabetical order.
3. For the trees in Q.1 and 2 give example of the following :
Leaves, internal vertex, siblings, root, ancestors , descendants
4. Traverse the given tree T in preorder , postorder and Inorder:



munotes.in