Teacher resources and professional development across the curriculum
Teacher professional development and classroom resources across the curriculum
The set of ideas we now call "network theory" can be traced back to the work of the great Swiss mathematician, Leonhard Euler. In the early-to-mid 1700s, Euler lived in the kingdom of Prussia in the town of Königsberg, now known as Kaliningrad, Russia. Through the town ran the river Pregel, and within the river were two small islands. These islands and the mainland were connected by seven bridges, as shown below.
A popular pastime among the city's residents was to look for a path through town that traversed all seven bridges without crossing the same bridge twice. Euler became intrigued by this problem. He recognized that the solution had nothing to do with any of the distances involved, but rather with the way in which the landmasses were connected to each other. He assigned each destination a letter and used pairs of letters to denote bridges. In modern mathematical language, each destination is called a "node" or "vertex" and each bridge is called an "edge." The problem can be simply represented in an image of four nodes and seven edges such as this:
By abstracting the Königsberg bridges problem, Euler was able to prove that there is no possible path that crosses each bridge exactly once. To do this, he looked at how many connections each node has; mathematicians now call this quantity a node's degree.
Euler realized that for such a theoretical ideal path to exist, it would have to be the case that at any "interior" (neither starting nor finishing) node of the walk, upon reaching the node by one bridge, there would have to be a way to depart the node by another bridge that had not been used yet. That is, if one was able to arrive at a node via one edge, one would have to be able to leave that same node via a different edge. Thus, as long as each interior node has an even number of connections, a path that contains every edge, now known as an Eulerian path, is potentially possible. Euler also realized that if we assume that the theoretical journey ends at a different node than the one at which it begins, then both the starting and finishing nodes must be of odd degree.
Changing the problem slightly, Euler also knew that if one is required to start and finish at the same node and walk a path that covers every edge only once, all nodes must be of even degree. We now call such a route an Eulerian cycle.
Euler's observation is now regarded as the first theorem in graph theory. It is also regarded as the first observation in topology, the study of fundamental properties of shape—those properties, such as connectivity, that don't change under stretching or squashing. As with many new fields of study, it took a while for others to join the endeavor. It wasn't until nearly a century later that other mathematicians began to expand on this work begun by Euler.
The Irish mathematician William Hamilton picked up the torch in the middle of the 19th century. His focus, like Euler's, was on whether or not certain networks admitted cycles. Hamilton is credited with defining a new type of cycle, one that, rather than covering every edge of a network, visits every node exactly once. This type of path is now commonly known as a Hamilton cycle, an example of which we saw briefly in Section 2.5 of Combinatorics Counts.
Questions about cycles in networks continued to provide fertile ground for post-Euler thinkers concerned with networks. This search led to the identification and classification of different types of networks. One of the simplest types of networks that have been identified is the tree. A German physicist, Gustav Kirchoff, known primarily for his laws concerning electrical circuits, was the first to record studies of something like network trees in the mid-1800s. These organizational structures will be familiar to anyone who has filled out a tournament bracket.
In a tree, every node is connected to every other node by exactly one path. This is different than the network of the Königsberg bridges, in which some nodes are connected via multiple paths.
If two nodes are connected by multiple paths, the length of the shortest of those paths defines the distance between the two nodes. The average distance in a network is the sum of all possible distances divided by how many there are. Cycles, paths, distance, and average distance are but a few of the characteristics of networks that can be mathematically studied. As the body of network theory grew, mathematicians developed more tools that enabled them to study and classify different networks and their properties.
A network is generally a real-world system of elements and their connections. There are two main ways that mathematicians abstract networks so that they can be more easily studied. The first, and most fundamental, way was pioneered by Euler; a network can be represented abstractly as a set of elements (the vertices or nodes) as well as a set of pairs (subsets of size two) of those elements, representing edges. For example, one way to represent a certain graph might be the set {A, B, C, D} (the set of vertices) together with the set of pairs {AB, BC, AD, AC, CD} that indicate the edges. We can tell from this representation that the graph has four nodes and five edges connecting them. It might be easier, however, to visualize this network as below:
Note that the edge BD is not included in the set of node pairs and thus does not appear in the visual representation of the network.
Mathematicians refer to this sort of diagram that relates nodes and edges as a "graph." The connections are just as important as the things they are connecting. As you can see, these graphs are slightly different than the ones composed of points on the coordinate plane that are commonly studied in school—in other words, in network theory we're not concerned with graphs of functions! In the most basic notion of a graph, all nodes are considered to be indistinguishable from each other, as are all edges. This is the first big abstraction in graph theory. Real networks are not made up of identical elements that all connect to each other via the same relationship. Making these assumptions, however, serves as a starting point for analysis.
By looking at a graph, we are better able to visualize and interpret the connections between elements. A key question is that of connectivity. We say that a graph is connected if, starting at any node, there exists a path to every other node in the network, no matter how circuitous.
Connectedness is important in many different real-world networks. With the power grid, if a house, block, or neighborhood is disconnected, it has no electricity. If a social group is connected, then every person is acquainted with every other member, although there may be intermediaries—"friends of friends" and such. It's not clear whether or not all the people on earth form a connected network, for there may not be a chain of acquaintances linking the most remote Mongolian nomad to a native living in the Amazon rainforest. We'll explore this idea in more detail a bit later.
Even when a network is not connected, there may be a sub-network that is. The Internet connects a large number of computers around the planet. Not all computers, however, connect to the Internet. Hence, the Internet represents what is known as a "connected component" of the network of all computers. There are other connected components, such as the secure computer networks run by the CIA and the Department of Defense. These connected components are isolated from the Internet and from each other.
While we're on the subject of computer networks, it's worth pointing out that the World Wide Web is a "directed network." This means that connections in cyberspace are not necessarily "two-way streets." For example, a blogger can post a link to a site, but that site doesn't necessarily have to link back to the referring blog.
The system of phone lines and other physical (including wireless) connections that make up the Internet, however, is an undirected network. These physical connections are two-way streets, although not all sites use this capability.
Let's return for a minute to the network of all people on earth. If it turns out that this network is indeed connected, then the chain of acquaintances that connects the two most remote people, say the Mongolian nomad and the Amazon native, is another quantity of interest known as the "diameter." The diameter of a graph or network is the longest possible distance between two nodes. Recall that we specifically defined distance as the shortest path between two nodes, so the diameter of a network is actually the "longest shortest path."
Finally, assuming that all nodes and edges are of equal value facilitates observations about networks and the graphs that represent them. This assumption can make things too simple sometimes, and important features may be missed. Graphs that assign different values to the edges are known as "weighted graphs." We explored weighted graphs somewhat in our discussion of the problem concerning the traveling salesperson in the unit: Combinatorics Counts.
The discoveries of Euler, Hamilton, Kirchoff, and others, formed a foundation for future mathematicians to continue the study and classification of graphs and their properties. Euler's theorem was the first such observation, but it was far from the last. Properties such as average distance, diameter, and connectedness became important tools for studying networks. As mathematicians learned to see networks as structures worthy of study in their own right, they began to identify and understand a range of different types of networks and the graphs that represent them. One of these types, random networks, is the subject of our next section.
Next: 11.3 Random Networks