Appendix 1 - Graph theory applied to topology analysis

Summary

The natural framework for a correct mathematical description of complex networks is graph theory. The origins of graph theory can be traced back to the pioneering work of Euler to solve the Königsberg bridges problem (Euler, 1736), and has now reached a maturity in which a wealth of results of immediate applicability are useful for the understanding of real complex networks. In this appendix we shall provide a cursory introduction to the main definitions and concepts of graph theory, useful for the analysis of real networks. The main sources followed are the books by Chartrand and Lesniak (1986), Bollobás (1998), and Bollobás (1985), as well as the review articles by Albert and Barabási (2002), Dorogovtsev and Mendes (2002), and Newman (2003), covering more recent aspects.

Graphs and subgraphs

An undirected graph G is defined by a pair of sets G = (V, E), where V is a non-empty countable set of elements, called vertices or nodes, and E is a set of unordered pairs of different vertices, called edges or links. Throughtout the book a vertex is reffered to by its order i in the set V. The edge (i, j) joins the vertices i and j, which are said to be adjacent or connected. The total number of vertices in the graph (the cardinality of the set V) is denoted as N, the size of the graph.