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.
Even and Odd Degree'sBack to Top
Graph Theory Shortest PathBack to Top
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
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 TheoryBack to Top
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 TheoryBack to Top
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 TheoryBack to Top
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.