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

Permutation

Permutation

1. In how many ways can 6 persons be arranged at a random table so that 2 particular persons may sit together?

Ans:
 i)  Arrange with respect to table: Taking 2 particular persons as one person, we are to arrange 5 (=1+4) persons in 5!. Again 2 persons can be arranged among themselves in 2! ways.

So required no. of arrangement = 5! x 2! =120 x 2=240


ii) Arrangement with respect to each other : At first 2 particular persons can be arranged themselves in 2! ways. Keeping them fixed & taking   as one person, all the 5 persons can be arranged in (5-1)!=4! ways.

So required no. of ways=4! x 2!=24 x 2=48

Some Important Definition of Graph Theory

1. Self –Loop:- An edge whose end vertices are same is called a self-loop.

2. Simple Graph:- A graph having no parallel edges and no self loops is called simple graph.

Some Important Theorem of Graph Theory

Some Important Theorem of Graph Theory

1. The maximum degree of any vertex in a graph with n vertices is n-1.

2. The maximum number of edges in a connected simple graph with n vertices is n(n-1)/2.