Main Data History
Show Index Toggle 0 comments

Graph Theory

In discrete mathematics, graphs are used to show concepts of networks or structures in a mathematical way. In particular, a graph consists of vertices \(\left(V\right)\), that is a finite set and a set of edges \(\left(E\right)\). Each edge has at least one vertex connected to it and can also be described as its endpoint. And edge is what connects these vertices or endpoints.

Common graphs: 

Simple graph- every edge is connected to two different vertices; no two edges can be connected to the same pair of vertices. 

Multigraphs- These graphs are called multi because unlike simple graphs there can be many edges connected to the same two vertices. 

Pseudograph- may consists of multiple edges (loops) and are also non simple. 

There are many types of graphs when looking into graph theory. Some of the two basics are directed and undirected. A directed graph is a graph that contains edges connected by one vertex to the next. An undirected graph however, has vertices that are connected by edges that are bidirection. 

Graph theory also consists of graphs that apply different rules such as the Eulerian graph and the Hamiltonian graph. The Eulerian graph is a graph that has an even degree for each of its vertices and has to be connected.

A Hamiltonian graph on the other hand is Hamiltonian if it contains a Hamiltonian cycle such that the graph can touch each vertex exactly one time and does not have to teach each edge.