BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Friday , July 28 2017
Home / Uncategorized / Definition of Graph| Discrete mathematics

# Definition of Graph| Discrete mathematics

Graph: A graph is said to be planner if it can be drawn on a plane in such a way that no edges cross one another except of course at common vertices.

Finite region and infinite region: A region is said to be finite if it is area is finite and infinite if its area is infinite.

Degree of regions: The number of edges on the boundary of a region is degree of regions.

When an edge occurs on the boundary it contributes two to the degree.

∴ Sum of degree of region =2.e

Note that: In a simple graph (not contain a loop) there is at least three edges or vertices for a finite region.

Directed graph: A directed graph or digraph is defined abstractly as an ordered pair (V.E) where (1) the elements of the set V are called vertices or nodes or point.

(2) The elements of the set E are ordered pair (u,v) of vertices called arc’s or directed edge or simply edge.

## Isolated vertex or point: A vertex is said to be isolated vertex or point if there is no edge with it.

Degree of vertex: The degree of a vertex in a graph G, written deg(v) is equal to the number of edge in G which contain v.

Isomorphism: Let G1=G1(V1, E1) and G2=G2(V2, E2) be two graph, then G1 is said to be isomorphic to G2 if there is a one to one function φ from V1 to V2 such that

(i) If uv is an edge in E1 , then φ(u) φ(v) is an edge in E2.

(ii) Every edge in E2 has the form φ′(u) φ′(v) for some edge uv∈E1.

G1 is isomorphism to G2 then G1≅G2.

If G1 and G2 isomorphic graph then G1 and G2 have the

(i) Same number of edge.

(ii) Same number of vertices.

(iii) Same degree sequence.

Sub-graph: Let G =(V, E) be a graph. A graph G′ = (V′, E′) is said to be a sub-graph of G if E′ is a subset of E and V′ is a subset of V such that the edges in E′ are incident only with the vertices in V′.

Example:

Spanning sub-graph: A sub-graph G′ of a graph G is said to be spanning sub-graph if it contains all the vertices of G.

## Complement of sub-graph: The complement of a sub-graph G′ = (V′, E′) with respect to the graph G is another sub-graph G″ = (V″, E″) such that

E″ is equal to E- E′ and V″ contains only the vertices with which the edges in E″ are incident. For example Fg-2 shows the complement of the sub-graph in Fig-1.

Complete Graph: The simple graph that contains exactly one edge between each pair of distinct vertices is called a called complete graph. It is denoted by Kn where, n is the number of vertices.

## Regular graph: A graph G is regular of degree K or K-regular if every vertex has degree K. In other words a graph is regular if vertex has the same degree.

Path: A path is a sequence of edges that begins at a vertex of a graph and travel along edges of the graph always connecting pairs of adjacent vertices.

Circuit or Cycle: A path of length n≥1 that begins and ends at the same vertex is called a circuit or cycle.

Simple path: A path or circuit is simple if does not contain the same edge more than once.

### Elementary path: A path is elementary if it does not contain the same vertex more than once.

Walk: A walk in a graph is an alternating sequence of vertices and edges beginning and ending with a vertex in which vertex is incident with the edge which follows and the last vertex is incident with the edge which precedes it.

Trail: A walk in which all edges are distinct is called a trail.

Example:

## For n ≥ 1, established that the integer n(7n^2 + 5) is of the form 6k

Solution: According to division algorithm, we have n = 6q + r ; 0 ≤ ...