Graph Theory for graduates level PPT by Biswas.pptx

It is for the graduation level mathematics

1. CONTENTS   TOPIC PAGES 1.GRAPH THEORY…………………………………………….1-25 (a) Introduction (b) Graph isomorphism & Graph operation (c) Walks, paths & circuits (d) Applications (e) Shortest Path 2. NUMBER THEORY………………………………………….26-42 (a) Introduction (b) Divisibility (c) Modular Arithmetic (d) Famous Number Theory (e) Application of number theory

2. 1 Graph theory In mathematics, graph theory is the study of graphs, which are mathematical structures, used to model pair wise relations between objects. A graph in this context is made up of vertices, nodes, or points which are connected by edges, arcs, or lines. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another 1.1 History The Konigsberg Bridge problem In the present century, there have already been a great many rediscoveries of graph theory which can only mention most briefly. Euler (1707-1782) becomes the father of graph theory as well as Topology. The paper written by Leonhard Euler on the Seven Bridges of Konigsberg and published in 1736 is regarded as the first paper in the history of graph theory. This paper, as well as the one written by Vandermonde on the knight problem, carried on with the analysis situs initiated by Leibniz. Euler's formula relating the number of edges, vertices, and faces of a convex polyhedron was studied and generalized by Cauchy and L'Huilier , and represents the beginning of the branch of mathematics known as topology.

3. Definitions There is large number of definitions in graph theory. The following are some of the more basic ways of defining graphs and related mathematical structure

4. TERMINOLOGY 2.1 Loop: an edge of the graph that joins a node to itself is called loop or self-loop i.e., a loop is an edge (Vi, vj ) where vj . 2.2 Multigraph: In a multigraph no loops are allowed but more than one edge can join two vertices, these edges are called multiple edges or parallel edges and graph is called multigraph 2.3 Directed & Un-directed graph: If each edge of graph G has a direction then the graph is called Directed Graph (Example of directed graph fig. 1). In Directed Graph each edge is represented by an arrow or direction curve from initial point u Ofe to the terminal point v (fig.2). If each edge of G has nodirection then the graph is called as An Un--Directed Graph. 2.4 Pseudo graph: a graph with loops and multiple edges are allowed, is called a pseudo graph 2.5 Simple graph: a graph which has neither loops nor multiple edges

5. .6 Finite and Infinite graphs: a graph with finite number of vertices as well as a finite number of edges is called finite graph. Otherwise infinite graph. 2.7 Degree Of vertex: The number of edges incident on a vertex with self-loops is called the degree of a vertex vj and denoted by degG ( vj ) or deg vj or d( vj ). 2.8 Isolated and Pendent vertices: A vertex has no incident edge is called an Isolated vertex. In other words, isolated vertices are those with zero degree. A vertex of degree one is called Pendent vertex or End vertex.

6. 3 Types of Graphs   3.1 Null Graph: A graph which contains only isolated node, is called a null graph i.e., the set of edges in the graph is empty. Null graph is denoted on n vertices by Nn N4 is shown in the finger 8. 3.2 Complete Graph: A simple graph G is said to be complete if every vertex in G is connected with every other vertex. 3.3 Regular Graph: A graph, in which all the vertices are of Equal degree, is called a Regular Graph. If the degree of each vertex is r, then the graph is called a regular graph of degree r.

7. The cycles C3 and C6 are shown in Fig 10. Wheels: The wheel VVn is obtained when an additional vertex to the cycle Cn, for n23, and connect this new vertex to each of the n vertices in Cn, by new edges. The wheels W3, W4, W5 and W6are displayed in the Fig 11.

8. Platonic Graph: the graph formed by edges and vertices of five regular(platonic) solids-The tetrahedron, octahedron, cube, dodecahedron and icosahedrons.   Tetrahedron Octahedron Cube Icosahedron Dodecahedron N-cube : The N-cube denoted by (On, is the graph that has vertices representing the 2 11 bit strings of length n. The adjacent if and only if the bit strings that they represent differ in exactly one bit position. The graphs QI are displayed in the figure 13. Thus Qnhas 2 n vertices and n.2 n I edges, and is regular of degree n

9. 4.GRAPH ISOMORPHISM and GRAPH OPERATIONS: 4.1 Graph isomorphism: Two graphs G and G' are said to be isomorphic to each other if there is a one-to-one correspondence (bijection) between their vertices and between their edges such that the incidence relationship is preserved. Graph v Correspondence of vertices Correspondence of edges f(a) = VI f(l) = el f(b) = v2 f(c) = v3 f(d) = v4 f(e) = v5 f(5) = e5

10. Adjacency also preserved. Therefore G and G' are said to be isomorphic. The following graphs are isomorphic to each other. i.e two different ways of drawing the same graph The following three graphs are isomorphic.

11. Introduction to Number Theory :- Number theory is a branch of mathematics which helps to study the set of positive whole numbers, say 1, 2, 3, 4, 5, 6,. . . , which are also called the set of natural numbers and sometimes called “higher arithmetic”. In number theory, the numbers are classified into different types, such as natural numbers, whole numbers, complex numbers, and so on. The sub-classifications of the natural number are given below: Prime numbers A prime number is a positive integer having exactly two factors, i.e. 1 and the number itself. If p is a prime, then its only factors are necessarily 1 and p itself. Any number that does not follow this is termed a composite number, which can be factored into other positive integers. Another way of defining it is a positive number or integer, which is not a product of any other two positive integers other than 1 and the number itself.

12. History of Prime Numbers The prime number was discovered by Eratosthenes (275-194 B.C., Greece). He took the example of a sieve to filter out the prime numbers from a list of natural numbers and drain out the composite numbers. Students can practice this method by writing the positive integers from 1 to 100, circling the prime numbers, and putting a cross mark on composites. This kind of activity refers to the Sieve of Eratosthenes. Properties of Prime Numbers Some of the properties of prime numbers are listed below: Every number greater than 1 can be divided by at least one prime number. Every even positive integer greater than 2 can be expressed as the sum of two primes. Except 2, all other prime numbers are odd. In other words, we can say that 2 is the only even prime number. Two prime numbers are always coprime to each other. Each composite number can be factored into prime factors and individually all of these are unique in nature.

13. Divisibility If a and b are integers, a divides b if there is an integer c such that ac = b. The notation a | b means that a divides b. For example, 3 | 6, since 3 · 2 = 6. And −2 | 10, since (−2)·(−5) = 10. Also, 3471 | 0, since 3471 · 0 = 0. Remarks. (a) Be careful not to confuse “a | b” with “a/b” or “a ÷ b”. The notation “a | b” is read “a divides b”, which is a statement — a complete sentence which could be either true or false. On the other hand, “a ÷ b” is read “a divided by b”. This is an expression, not a complete sentence. Compare “6 divides 18” with “18 divided by 6” and be sure you understand the difference.

14. Modular Arithmetic Definition (mod). If a is an integer and n is a positive integer, then a mod n is the remainder obtained when we divide a by n using the Euclidean Algorithm. Famous Number Theory Fundamental Theorem of Arithmetic “Every natural number can be expressed in the form of the product of the power of its primes” Ex. 35 = 5 120 = etc.  

15. 2 Fermat's little theorem   States that “if  p  is a prime number, then for any integer  a , the number  a p  −  a  is an integer multiple of  p . In the notation of modular arithmetic, this is expressed as   For example, if  a  = 2  and  p  = 7 , then  2 7  = 128 , and  128 − 2 = 126 = 7 × 18  is an integer multiple of  7 . If  a  is not divisible by  p , that is, if  a  is coprime to p , then Fermat's little theorem is equivalent to the statement that  a p  − 1  − 1  is an integer multiple of  p , or in symbols:   For example, if   a  = 2   and   p  = 7 , then   2 6  = 64 , and   64 − 1 = 63 = 7 × 9   is thus a multiple of   7 .

16. Chinese Remainder Theorem Suppose are pairwise relatively prime integers   that is, any two of them are relatively prime. Then, for any integers the system of congruences : : has a solution that is unique modulo the product