Graphs are a mathematical structure composed of a set of elements, and a set of connection between them. Due to their intuitive representation, graphs are widely employed in many different fields and, in particular, in systems biology and bioinformatics. In fact, they are used to model biological networks is several case studies, but also to represent data structures in different algorithmic procedures for solving bioinformatic problems. One of the key points of this widespread adoption is also related to the strong mathematical formulation behind them. In this article, we will introduce the basic concepts of graphs, starting from their definition and the description of simple notions. We will also describe specific types of graphs, like bipartite graphs and multigraphs, and we will explain two possible representations, namely adjacency lists and adjacency matrix. Finally, we will focus on bipartite graphs, by proposing an intuitive procedure to check if a graph is bipartite.

Beretta, S., Denti, L., Previtali, M. (2019). Graph theory and definitions. In Encyclopedia of Bioinformatics and Computational Biology: ABC of Bioinformatics (pp. 922-927). Elsevier [10.1016/B978-0-12-809633-8.20421-4].

Graph theory and definitions

Beretta S.;Denti L.;Previtali M.
2019

Abstract

Graphs are a mathematical structure composed of a set of elements, and a set of connection between them. Due to their intuitive representation, graphs are widely employed in many different fields and, in particular, in systems biology and bioinformatics. In fact, they are used to model biological networks is several case studies, but also to represent data structures in different algorithmic procedures for solving bioinformatic problems. One of the key points of this widespread adoption is also related to the strong mathematical formulation behind them. In this article, we will introduce the basic concepts of graphs, starting from their definition and the description of simple notions. We will also describe specific types of graphs, like bipartite graphs and multigraphs, and we will explain two possible representations, namely adjacency lists and adjacency matrix. Finally, we will focus on bipartite graphs, by proposing an intuitive procedure to check if a graph is bipartite.
Capitolo o saggio
Adjacency list; Adjacency matrix; Bipartite graph; Directed graph; Multi-graphs; Undirected graph; Weighted graph;
English
Encyclopedia of Bioinformatics and Computational Biology: ABC of Bioinformatics
6-set-2018
2019
978-0-12-811432-2
1
Elsevier
922
927
Beretta, S., Denti, L., Previtali, M. (2019). Graph theory and definitions. In Encyclopedia of Bioinformatics and Computational Biology: ABC of Bioinformatics (pp. 922-927). Elsevier [10.1016/B978-0-12-809633-8.20421-4].
none
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/311008
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
Social impact