Recurrence Relations

Basic concept: 

          Recurrence relations are recursive definitions of mathematical functions or sequences. For example, the recurrence relation

     g(n) = g(n-1) + (2n -1)
     g(0) = 0


defines the function f(n) = n2, and the recurrence relation

ISOMORPHISM OF GRAPH

Two Graphs G₁(V₁,E₁) and G₂(V₂,E₂) are isomorphic if there is a bijective (one to one and onto) mapping f:V₁ –> V₂  that preserves adjacency that is a and b are adjacent in G₁ if and only if f(a) and f(b) are adjacent in G₂, for all a, b belongs to G₁. Such a correspondence f is called graph isomorphism 

Adjacency & Incidence Matrices

ADJACENCY MATRICES:

           

            Suppose G(V,E) is a simple graph with n vertices v₁,v₂,….,v_n. The adjacency matrix or sometimes called connection matrix of the graph G(V,E), denoted by A(G) is a matrix (a_ij)_{n x n} (with respect to the particular ordering of vertices) such that,

                        a_ij=1, if there is an edge between i th and j th vertices

                           =0, if there is no edge between i th and j th vertices

Subgraph

SUBGRAPH:

            A subgraph of a graph G(V,E) is a graph H(W,F) where W subset equal to V and F subset equal to   E. If W sub set V and F sub set E , then H is called the proper subgraph of G, if W=V, then H is called a spanning subgraph of G. A spanning subgraph of G need not contain all its edges. The graph H shown in below is a subgraph of K₅ . 

Some Special Simple Graph

A) Complete Graph:

                 A simple graph that contains exactly one edge between every pair of vertices. The complete graph on n vertices is denoted by Kn

Mathematical Logic

Mathematical Logic

1. Construct the truth table for ~(~p ^ ~q)

p	q	~p	~q	~p ^ ~q	~(~p ^ ~q)
T	T	F	F	F	T
T	F	F	T	F	T
F	T	T	F	F	T
F	F	T	T	T	F

Mathematical Logic

	Unioun operation						Intersection Operation
	p	q	pUq				p	q	p^q
	T	T	T				T	T	T
	T	F	T				T	F	F
	F	T	T				F	T	F
	F	F	F				F	F	F