Learning Made Easy

Lemma: (Pumping Lemma) If L is a regular language, then there exists a positive integer p (the pumping length) such that every string s ∈  L,|s | ≥p, can be partitioned into three pieces,s=xyz, such that the following conditions hold: 1.|y| > 0, 2.|xy| ≤p, and 3.for each i ≥0, xy i z Standard Example: 1.L={a n b n | n=0}is not regular. 2.L={1 n | n is a prime number}is not regular. 3.L={0 i 1 j | i > j}is not regular.

An independent set   S   is a subset of   V   in   G   such that no two vertices in   S   are adjacent. I suppose that its name is meaning that vertices in an independent set   S   is independent on a set of edges in a graph  G . Like other vertex sets in graph theory, independent set has maximal and maximum sets as follows: The independent set  S  is  maximal  if  S  is not a proper subset of any independent set of  G. The independent set  S  is  maximum  if there is no other independent set has more vertices than  S . That is, a largest maximal independent set is called a maximum independent set. The maximum independent set problem is an NP-hard optimization problem.

Decomposition: ------------------------------- Let R be a relation schema A set of relation schemas { R1, R2,…, Rn } is a decomposition of R if R = R1 U R2 U …..U Rn Each Ri is a subset of R ( for i = 1,2…,n) Lossy Decomposition: When union of R1UR2UR3.......Rn is taken and output obtained from this does not match with original relation schema i.e. R that means there is loss of information and such type of decomposition is called as lossy decompostion. Lossless Decomposition : A decomposition of {R1,R2,R3,.............Rn} of a relation R is called a lossless decomposition is R is natural join of R1,R2.........Rn produces exactly relation R.

Some Graph Terminology: ==========================  Bipartite Graph  :  A  bipartite  graph is a graph  G  whose vertex set  V  can be partitioned into two non empty sets  V 1  and  V 2  in such a way that every edge of  G  joins a vertex in  V 1  to a vertex in  V 2. Star Graph : Suppose we start with  n  vertices, choose one special vertex and then draw edges from the special vertex to every other vertex. The graph we would obtain is called the star  on  n  vertices,  S n Wheel Graph : A wheel   on  n  vertices  W n  is a graph with  n  vertices  x 1 ,   x 2 , ...,  x n ,  with  x 1  having degree  n-1  and all the other vertices having degree  3.  The vertex  x 1  is adjacent to all the other vertices, and for  i=2, ..., n-1 ,  x i  is adjacent to  x i+1 , and  x n-1  is adjacent to  x 2 . We shall assume that  n>3  in all the problems. Fig 22.1, The wheel graph  W 51 Planar Graph: When a graph can be drawn without any of the edges crossing