Graph Theory is the study of mathematical models consisting of two parts: edges and vertices. These elements represent objects and their relationship with each other and they create easy-to-understand models that used in many different sectors.
For example, Graph could be applied for modeling connection between cities, the study of atoms and molecules, DNA Sequencing, and many more. Moreover, Graph Theory also provides the basis of many Operations Research problems description such as Travelling Salesman Problem, Classical Transportation Problem, and Classical Postman Problem. Graphs are represented by diagrams that contain points (representing vertices) and lines (representing vertices).
In general, graphs have three distinct types: Undirected, Directed, and Weighted Graph. The undirected graph has edges without any specified directions. Hence, an edge from A to B is identical to an edge from B to A.
Simple examples of undirected edges are roads between cities since these roads are mostly two-way roads. In contrast to an undirected graph, a directed graph (Digraph) has edges with specified direction, meaning an edge from A to B is unavailable for the other way around (B to A). A simple example of directed edges is one-way roads.
Lastly, a weighted graph contains a specific value or ‘weight’ attached to each edge which represents variables such as cost or distance. Moreover, both undirected and directed graphs could be modified to be a weighted graph depending on the graph’s representation.
Even humans understand graphs’ representation easily, it is a challenge for computers to decipher graphs by their shape. Therefore, another model should be used to make the model recognizable by computers.
Three popular models for this purpose are adjacency matrix, incidence matrix, and adjacency list. Adjacency Matrix is a binary matrix with vertices-vertices pairs (for row and column). Two vertices are adjacent to each other when a connection between them exists.
If two vertices are adjacent, then the value in the matrix is 1, otherwise, it is 0. Incidence Matrix is also similar to Adjacency Matrix; However, instead of vertices-vertices pairs, Incidence Matrix has vertices-edges pairs. Even both matrices are simple and easy to use, they store redundant information and require a long time for searching data since the computers have to search in each row and column.
Comments