Graph theory

Network Theory: 3 Graph Theory

• Report rights infringement
• published: 18 Apr 2015
• views: 5687

In this lecture we start to lay down some of our basic language for talking about networks that comes to us from graph theory​ a relatively new area of mathematics that studies the properties of graphs. For full courses see: http://complexitylearning.io Twitter: https://twitter.com/complexitylearn Facebook: https://goo.gl/ggxGMT G+: https://goo.gl/G6zTMg Transcription: When we hear the word network all sorts of things spring to mind like social networks and the Internet in particular, but the power of network theory is really in its high degree of abstraction, so the first thing for us to do is to try and start back at the beginning by forgetting what we think we know about networks and embrace the abstract language of networks what is called 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. 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 consist 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 quantifies, 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 define 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 and we will be often using this latter term during the course. The nodes belonging to an edge are called the ends, endpoints, or end vertices of the edge. Within graph theory networks are called graphs and a graph is define as a set of edges and a set vertices. A simple graph does not contain loops or multiple edges, but a multigraph is a graph with multiple edges between nodes. So where as a simple graph of a transpiration system would just tell us if there is a connection between two cities, a multigraph 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 round, 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.