Graph and Graph Models - Discrete Mathematics

What is a graph?

The two different structures of discrete mathematics are graphs and trees. The set of lines interconnect the set of points in a graph. The set of points are called as nodes and the set of lines as edges. In the areas of mathematics, engineering and computer science, the study of graph is very important. The study of graph is also known as Graph theory.

Definition

A graph (denoted as G=(V,E)) consists of a non-empty set of vertices or nodes V and a set of edges E.

Example – For instance, a graph is considered as G=(V,E)) where V={a,b,c,d}and E={{a,b},{a,c},{b,c},{c,d}}

Graph

Degree of a Vertex – The number of edges that are incident with the vertex V is termed as the degree of a vertex V of the graph G, denoted by deg (V).

Vertex
Degree
Even / Odd
a
2
even
b
2
even
c
3
odd
d
1
odd

Even and Odd Vertex – The vertex is even when the degree of vertex is even and the vertex is odd when the degree of vertex is odd.

Degree of a Vertex – The largest vertex degree of that particular graph is considered as the degree of the graph.

The Handshaking Lemma – The sum of all the degrees of the vertices is equal to double the number of edges.

What are the different types of Graphs?

The following are the different types of graphs available:

Null Graph

A graph with no edges is known as a null graph. The null graph of n vertices is denoted by

Null Graph

Simple Graph

When the graph is undirected without any loops or multiple edges, such a graph is known as Simple/strict graph.

Simple Graph

Multi-Graph

When between the same set of vertices, multiple edges are allowed, it is known as a Multigraph. Multigraph have at least one loop or multiple edges.

Multi Graph

Directed and Undirected Graph

When the ordered vertex pair make up the edge set, then the graph G=(V,E) is known as a directed graph and when the unordered vertex pair make up the edge set, then the graph is known as a undirected graph.

Directed Graph

Undirected Graph

Connected and Disconnected Graph

If any two vertices of a graph are connected by a path, the graph is said to be connected. If at least two vertices of the graph are not connected by a path, the graph is said to be disconnected. If a graph G is disconnected, then every maximal connected subgraph of G is called a connected component of the graph G.

Connected Graph

Disconnected Graph

Regular Graph

When all the vertices of the graph have same degree, the graph is said to be a regular graph. In a graph G of degree r, the degree of each of the vertex of G is r.

Regular Graph

Complete Graph

When exactly one edge joins every two vertices pair, the graph is said to be a complete graph. The complete graph with n vertices is denoted by

Complete Graph

Cycle Graph

The graph with a single cycle is known as a cycle graph. The cycle graph with n vertices is represented by

Cyclic Graph

Bipartite Graph

When graph G is split into two disjoint sets, V1 and V2, such that each of the vertex in V1 is joined to each of the vertex in V2 by each of the edge of the graph. And no edges in G should connect either two vertices in V1 or two vertices in V2 and such a graph is known as bipartite graph.

Bipartite Graph

Complete Bipartite Graph

In a bipartite graph, each vertex of the first set is joined to every single vertex in the second set, such a graph is known as complete Bipartite Graph and is denoted by

Complete Bipartite

In how many ways cab Graphs be represented?

A graph can be represented in two ways:

  • Adjacency Matrix
  • Adjacency List

Adjacency Matrix

A 2d array of size V×V where V is the number of vertices in a undirected graph, is known as an adjacency Matrix A[V][V] .

If there is an edge between

Then the value of

Otherwise the value is 0.

For a directed graph,

If there is an edge between

Then the value of

Otherwise the value is 0.

Adjacency Matrix of an Undirected Graph

For instance, consider the following undirected graph and construct the adjacency matrix -

Adjacency Undirected

For the above undirected graph, the adjacency matrix is as follows:

a
b
c
d
a
0
1
1
0
b
1
0
1
0
c
1
1
0
1
d
0
0
1
0

Adjacency Matrix of a Directed Graph

For instance, consider the following directed graph and construct the adjacency matrix -

Adjacency Directed

For the above undirected graph, the adjacency matrix is as follows:

a
b
c
d
a
0
1
1
0
b
0
0
1
0
c
0
0
0
1
d
0
0
0
0

Adjacency List

A graph G with V number of vertices is represented by an array (A[V]) of the linked list in adjacency list.

The linked list of the vertices adjacent to the Vx−th vertex is represented by the entry

For an undirected graph, the adjacency list is depicted below:

Adjacency List

Planar vs. Non-planar graph

Planar graph – Without crossing the edges when a graph can be drawn plane, the graph is called as a planar graph. It is known as embedding the graph in the plane.

Planar Graph

Non-planar graph – When it is not possible to draw a graph in a plane without crossing edges, it is non-planar graph.

Non Planar Graph

What is Isomorphism?

When the same numbers of vertices are connected in the same way in two different graphs G and H, then they are called as isomorphic graphs, represented as G≅H.

The graphs are said to be non-isomorphism when any one of the following conditions appears:

  • Difference in the number of connected components
  • Difference in vertex-set cardinalities
  • Difference in edge-set cardinalities
  • Difference in the sequences of degree

Example

The examples for isomorphic graphs is depicted below:

Isomorphism

What is Homomorphism?

The mapping between the graphs G and H in such a way that h:G→H, such that (x,y)∈E(G)→(h(x),h(y))∈E(H). The adjacent vertices of graph G are mapped to the adjacent vertices of graph H.

Properties of Homomorphisms

  • For bijective mapping, a homomorphism is said to be an isomorphism.
  • The edges and connectedness of the graph is always preserved by homomorphism.
  • The compositions of homomorphisms are also homomorphisms.
  • Identification of the presence of homomorphic graph of another graph is a big problem.

What are Euler Graphs?

If a graph has a closed trail including every edge of the graph G, such a connected graph is known as Euler graph. The path that is used by every edge only once is the Euler path which starts and ends at different vertices.

The circuit that uses every edge of the graph only once is known as Euler circuit. Euler circuit starts and ends at the same vertex. An Euler graph is a connected graph when all the vertices of G are of even degree.

Euler Graph

The above graph is an Euler graph as “a1b2c3d4e5c6f7g” covers all the edges of the graph.

Non euler graph

What are Hamiltonian Graphs?

If there is a cycle in the connected graph that includes every vertex of G is known as Hamiltonian cycle. The walk that passes through each vertex exactly once in a graph G is known as Hamiltonian walk.

If G is a simple graph with n vertices, where

for each vertex v, then the graph G is Hamiltonian graph. This is called Dirac's Theorem.

If G is a simple graph with n vertices, where

for each pair of non-adjacent vertices x and y, then the graph GG is Hamiltonian graph. This is called Ore's theorem.

Hamiltonian Graph

Non Hamiltonian Graph

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Discrete Mathematics Topics