# Graph Theory

Updated: Sep 4, 2020

## Graph Theory

In the formal language of mathematics, a network is called a graph, and graph theory is the area of mathematics that studies these objects called graphs. Graph theory is a relatively new area of mathematics that gives us a formal language with which to describe networks. The first theory of graphs goes back to 1736. The first textbook came about in 1958 but most of the work within this field is less than a few decades old. In its essence, a graph is really very simple. It consists of just two parts, what are called vertices and edges. Firstly vertices, a vertex or node is a thing, that is to say, it is an entity, and we can ascribe some value to it. So a person is an example of a node, as is a car, planet, farm, city or molecule. All of these things have static properties that can be quantified, such as the color of our car, the size of our farm, or the weight of our molecule. Within network science vertices are more often called nodes, so we will be typically using this term during the course. Edges can be defined as a relation of some sort between two or more nodes. This connection may be tangible, as in the cables between computers on a network, or the roads between cities within a national transportation system. Or these edges may by be intangible, such as social relations of friendship. Edges may be also called links, ties or relations. The nodes belonging to an edge are called the ends, endpoints, or end vertices of the edge.

### Graphs

Within graph theory, networks are called graphs, and a graph is defined as a set of edges and a set vertices. A simple graph does not contain loops or multiple edges, but a multi-graph is a graph with multiple edges between nodes. Whereas a simple graph of a transportation system would just tell us if there is a connection between two cities, a multi-graph would show all the different connections between the two cities. Graphs can be directed or undirected. With an undirected graph, edges have no orientation. For example, a diplomatic relation between two nations may be mutual, and thus have no direction to the edge between the nodes. These undirected graphs have unordered pairs of nodes, that means we can just switch them around. If Jane and Paul are married, we can say Jane is married to Paul, or we can say Paul is married to Jane. It makes no difference, and thus it is an unordered pair.

### Directed Graphs

In contrast to an undirected graph, we have directed graphs, which is a set of nodes connected by edges, where the edges have a direction associated with them. That is typically denoted with arrows indicating the direction. For example, if we were drawing a graph of international trade, the graph might have arrows to indicate the direction to the flow of goods and services. Directed graphs have some order to the relations between nodes, and this can be quite important. A graph is a weighted graph if a number – a weight – is assigned to each edge. These numbers quantify the degree of interaction between the nodes or the volume of exchange. With the trading example above, if we wanted to convert this into a weighted graph, we would then ascribe a quantitative value to the amount of trade between the different nations.

### Multiplex Graphs

So this is the basic language of graphs, but we can extend this language to talk about graphs that have multiple types of edges and nodes, what are called multiplex networks that add a whole new level of complexity to our representation, allowing us to capture how different networks interrelate and overlap to affect each other.

1. Graph theory | Problems & Applications | Britannica. (2020). In: Encyclopædia Britannica. [online] Available at: https://www.britannica.com/topic/graph-theory [Accessed 4 Sep. 2020].

2. Ruohonen, K. (2013). GRAPH THEORY. [online] Available at: http://math.tut.fi/~ruohonen/GT_English.pdf.

3. Wikiwand. (2020). Multidimensional network | Wikiwand. [online] Available at: https://www.wikiwand.com/en/Multidimensional_network [Accessed 4 Sep. 2020].

29 views

Systems Innovation