Sales Toll Free No: 1-800-481-2338

Graphs in Discrete Mathematics

Top

Discrete mathematics is a distinct mathematical term rather than being continuous term. Graph, integers, etc. are the part of discrete mathematics it excludes the topics such as of Calculus and analysis, etc. or in short we can say discrete mathematics deals with the countable Sets. As such there is no specified definition of discrete mathematics.
Graph in discrete mathematics can be studied with the help of graph theory which is also considered as the part of combinatorics, but in the present era it is a separate branch of mathematics first investigated by D.König in the year 1930.

Also graphs are considered to be the prime subject in the discrete mathematics. Graph theory discrete mathematics is considered among the omnipresent model of both the natural and the structures which are made by man. They can mold many type structures and Relations such as method dynamics in physical, social and biological system. They have their several uses in many fields like in computer science they represent communication network, organization of data, help in the flow of computation, data organization, etc. in the field of mathematics, they can be used in the Geometry and also in many areas of topology. Also the group theory has a close link with the algebraic graph theory.

Discrete mathematics is also known as finite mathematics and the decision mathematics. As it is given above that it studies the countable Sets but it is different from continuous graph, we must not mix continuous graph with the graph theory. The graphs in discrete mathematics are of the many types few of them are simple graph, multi graph, directed graph, pseudo graph and many more. Now we will see brief description about these graphs:

1. The simple graphs are un- weighted and not in the particular direction and they have no loops but they have multiple edges.

2. The graphs which have multiple edges are multiple graphs.

3. The graphs which are connected with the Set of nodes and with its edges are directed graph.

4. Pseudo graph has the multiple edges and the graph loops connect them.

Even and Odd Degree's

Back to Top
A graph consists of nodes and edges, these edges are incident to a node and these nodes are also called as vertices of graph.
Degree in graph theory can be defined as number of edges incident to a vertex or node present in graph or we can say number of edges attached to vertex of graph is known as degree of that graph.
Degrees of a graph can be classified in two categories, that is even and odd degrees, let us now see definition of even and odd degree:
Even degree: Degree of vertex in a graph is even if number of edges incident on vertex is even.
In the graph shown above we can see that there are three vertices present in graph and each vertex in graph has two edges incident on them, so degree of each vertex is equals to 2 which is even. So each vertex in this graph has even degree.
Now we will discuss odd degree:
Odd degree: Degree of a vertex in a graph is odd if number of edges incident on a vertex is odd.
In graph shown above we can see that number of edges incident on vertices 'A' and 'D' is equals to 3 which is odd. So we can say that degree of vertices A = D = 3 and degree of vertices 'A' and 'D' is odd.
This is all about even and odd degrees in graph theory.

Graph Theory Shortest Path

Back to Top
In field of science, graph theory is one of the very important concepts which describes that how a graph models different type of mathematical structures and also it can be used for all those structures which are created by human beings.
Also graphs are ubiquitous models which may be useful for various Relations.
Graphs has wide use due to their practical importance. They can be implemented practically.
Wide use of graph is its use in to find out the shortest path and minimum cost in various transportation problems.
A graph can be referred to collection of vertices and edges. These vertices are also known as nodes, edges are basically used to connect nodes.
Nodes or vertices are indicated by Circle or dot and line between various nodes represent edges.
Edges can be undirected which are also known as asymmetric or undirected also called symmetric. These edges may be weighted or unweighted. Weighted edge refers that some distance exists between two nodes and unweighted edge means that there is no distance between two vertices.

Application of graph theory shortest path is the shortest path problem which targets to minimize the sum of weights of its edges which connects two or more vertices.
Graphs may be undirected in which the shortest path problem may be explained with following description:
Lets consider a weighted graph in which a Set 'X' of vertices, a set 'Y' of edges and f : E → R which is showing a weight function , and elements 'a' and 'b' of 'X', find a path 'Z', an order of edges from a to b of X so that
∑ f(z),
Where z ε Z,
Shows minimal path which is connecting a to b.
Shortest path problem may also be called as single - pair shortest path problem to differ it from single - source shortest path problem, single - destination shortest path problem, all-pairs shortest path problem.

Path in Graph Theory

Back to Top
Path can be defined as distance traveled by an object from one Point to another. Points are called vertices of the path. Let there be two vertices A and B, then path between these two vertices is called A – B path. The distance between these two points or vertices is known as edge. Hence a path may include several vertices and edges. The Set of vertices and edges actually forms a graph which is called path graph. A path graph can also be defined as set of nodes (vertices) and set of lines that connect these nodes.
Open path is a path in which first and last vertices are not connected. If first and last vertices are same, then this type of path will be called as cycle graph. If vertices are connected to each other by various edges in a sequence then this sequence of vertices in a graph is called as paths in graph theory.


Figure shown above has five vertices (nodes) and five edges (lines) to connect the vertices. Here first and last vertices that is vertex number 1 and 5 are distinct that’s why this type of graph is called as path graph. There is no meaning of length of lines in graph theory since lines are only used to show relationship between vertices. In above figure, node 1 is connected to node 2 and node 3. Edge is used to define this relationship. Various types of path graphs are directed graph, valued graph etc.

Cycle in Graph Theory

Back to Top
Cycle graph can be defined as a graph which is comprised of single cycle. In other words, if vertices in given graph are connected in a closed form then graph is called as cycle graph. A cycle graph may can also be referred to circular graph. In a cycle graph, if there are 'n' vertices then cycle graph will be denoted by C n and number of vertices (nodes) in C n is equals to the number of edges and degree of each vertex is 2 that is each vertex has exactly two edges which are incident to node (vertex). A cycle graph has common first and last vertex. This can be shown by the following figure.



In above figure, it is clear that first and last Point is ‘a’ that’s why this is called as cycle graph. Hence it can be said that cycle is a closed graph. If there are four vertices in the graph then it is called as 4 – cycle.
Cycle in graph theory can be Odd or even cycle. These two terms can be defined as follows. If there are odd Numbers of edges in a cycle graph then it will to odd cycle graph and if number of edges (lines) is even in cycle graph then this type of graph is called even cycle graph.
Degree of cycle graph is given for vertices and can be calculated by counting the number of lines meeting on that vertex.
Lets consider an example as shown below:



The degree of node ‘A’ in the above graph is three since there are three edges incident on it. Similarly the degree of B, C and D will be given as deg (B) = 2, deg (C) = 4 and deg (D) = 1.

Connectivity in Graph Theory

Back to Top
Connectivity is related to the network flow problems. It is used to find out the minimum number of vertices or edges which can be used to disconnect the remaining nodes from each other. Connectivity of a graph actually shows the robustness of the graph. If there are two nodes or vertices A and B, then they will be said connected if there is a path from A to B. Otherwise, they are disconnected.

Menger's theorem is one of the important theorems which is used to define the concept of connectivity in graphs. This theorem, actually describes the line (edge) connectivity of a graph in terms of the number of independent paths between vertices (nodes). Let’s try to understand the Menger's theorem. If A and B are the two vertices of a graph, then collection of paths between A and B is said free if none of the two vertices A and B share a vertex and if no two paths share an edge, then it is called as edge – dependent.

Let’s consider that maximum number of free paths between A and B is C′ (A, B) and highest number of edge free paths between A and B is written as D′ (A, B) then according to Menger's theorem, the local connectivity equals C′ (A, B) and local edge-connectivity equals D′ (A, B) for every pair of vertices A and B.
Let’s see Connectivity In Graph Theory.

If we denote the edge-connectivity by E then it will be defined as minimum number of edges which on removing, disconnects the graph. When E ≥ m, graph is called m-edge-connected graph. If we write Connectivity of Complete Graph by m (mk), then connectivity of complete graph m k is m – 1. Vertex Connectivity can be defined as smallest number of vertices, which when removed leaves the graph disconnected.