DISCRTE MATHS 

GRAPHS : It is simply a collection of  vertices & edges.It can be represented by G(V,E) where V ={v1,v2,.....,vn} & E={e1,e2,......,en}

                                                     

 

 

Here a graph with Vertices v1,v2,v3,v4 & edges e1,e2,e3,e4,e5 is given.

Imp. terms in graphs:

1.Degree :It is defined as no. of edges connected to a particular vertices.It is defined for vertices in graphs.it is represented by d(v).

                                  

 

 

in above graph d(v1)=d(v4)=3 & d(v2)=d(v3)=2

2.Self loop: when starting & end vertex are same then self loop forms.

For self loop d(v)=2.

  

3. Parallel edges: If there exists more than one edges b/w any two vertices of graph then those edges are said to be parallel edges.

4.Adjacency: When two vertices are connected through a common edge then those vertices are said to be adjacent &this property is called Adjacency.

             TYPES OF GRAPHS 

1.Undirected Graph: In a graph G, the set of vertices are V and the set of edges are e and each edge is associated with unordered pair of vertices V, then this graph is known as Undirected Graph. In other words, we can say that each pair of vertices is connected by a straight line and direction between two vertices are not there. for example, the graph G = (Set of vertices, Set of edges) = ({v₁, v₂, v₃}, {e₁, e₂, e₃}). Since, the graph has three vertices so it is a triangular shape as given figure below.

 

 

                         UNDIRECTED GRAPH

2.Directed Graph: A graph is called the Directed Graph if in a graph the set of vertices are V and the set of edges is E, consists the order pairs of elements of V. Generally we can say that each pair of vertices are connected by a straight lines or a direction between both the vertices exist. For example, a graph having the vertices are {v₁, v₂, v₃} and its edges are {e₁, e₂, e₃}). The shape of a graph is a triangular shape. The graph is shown below.

 Directed Graph

3. Mixed Graph: A mixed graph is the combination of both Directed Graph and Undirected GrapH. A Graph G is knwon as a Mixed Graph if some of the edges in a graph are directed and some are undirected, or we can say that some edges the directions are given and some edges not. For example, a graph with three set of vertices and three edges i.e. G = ({v₁, v₂, v₃}, {e₁, e₂, e₃}) drawn as

  Mixed Graph

4.  Null Graph: A graph in which all the verteices are isolated. then it is knwon as a Null graph i.e. a graph has no edges, only vertices called the Null Graph.

 Null Graph

5. Simple and Multiple Graph: A graph, in which there is no self loop graph and no parallel edges, then a graph is called a simple graph and a multi graph is a graph with multiple edges between the same vertices.

    
 Simple and Multiple Graph

6. Finite and Infinite Graph: If in a graph G, the set of edges and a vertices are finite then the graph is a finite graph else it is a called as a infinite graph.

    

Graph 1: Finite Graph                          Graph 2: Infinite Graph

 Finite and Infinite Graph

7. Connected and Disconnected Graph: A vertices are (v₁, v₂, v₃, v₄, v₅) with the edges (e₁, e₂, e₃, e₄, e₅, e₆, e₇, e₈).