Cyber-physical Systems

5Network

So far, we have introduced the key concepts used to demarcate systems, to characterize uncertainty by probability theory, and to define data and information as the basis of cyber realities. In all the previous chapters, we have indicated that different elements under analysis are related to each other, but without explicitly defining how. This chapter introduces the basics of graph theory and network sciences, which are the disciplines providing the fundamental concepts to evaluate structured relations between different elements [1]. We will first introduce the mathematical theory of graphs, which formalizes the relation between vertices by edges. Then, we will present how graph theory is employed in other domains to evaluate particular networks where nodes are connected with each other by links. Different network topologies will be presented together with illustrative applications, for example, in transportation and epidemiology. We will also indicate the main limitations and problems of network sciences, which concern the relation between theoretical models and actual physical processes. This chapter provides only a brief overview of the field; for interested readers, the interactive book Network Science [2] is highly recommended.

5.1 Introduction

Graph theory is a field in mathematics that deals with structures using pairwise relations. The field started with the study about the Seven Bridges of Königsberg by Euler [3]. The problem is described as follows [4