Graph Theory and Definitions

Graphs are mathematical structures consisting of a set of elements (nodes or vertices), and a set of connections among them (edges or arcs). Due to their intuitive representation, graphs are widely employed in several fields and, in particular, in systems biology and bioinformatics. In this latter context, graphs have been used to model biological networks in different case studies, but they are also exploited in data structures that are useful in different algorithms for problems in bioinformatics. One of the key points of this widespread adoption of graphs is also related to the strong mathematical formulation behind them. In this contribution, we will introduce the basic concepts of graphs, starting from their definition and the description of simple notions. We will also describe some well-known classes of graphs, like bipartite graphs and multigraphs, and we will introduce two renown representations, that is adjacency lists and adjacency matrix. We conclude this contribution with a focus on bipartite graphs, in particular presenting an intuitive algorithm to check whether a graph is bipartite or not.