###### Networks

Maths Applications (Year 12) - Graphs and Networks

Niamh Collie

Graphs** **are visual mathematical structures used to model points in a discrete set of data and the relationships between them. This definition is inclusive of network diagrams. There is a lot of terminology in the study of networks that are necessary to understand and describe them, so let's start with that.

# Definitions

**Network: **Graphs depicting a set of points (called vertices) that are connected by lines (called edges). They are used to model the pairings and relationships between these points in a set of discrete data. In the network graph below, data points A, B, C and D are represented and the relationships between them modelled.

**Vertex:** Junctions/points representing each discrete data point joined by lines, called edges. In the network graph A-D below, these are the blue dots. (Plural: vertices).

**Edge: **Lines connecting the vertices to one another. They show the relationships between each vertex. In the network graph A-D below, these are the orange lines.

**Multiple edges: **When two or more edges connect the same two vertices, they are known as multiple edges. In the network graph E-G below, they are the green lines.

**Loop: **A network with an edge that starts and ends at the same vertex is said to contain a loop. In the network graph H-J below, it is the pink line. Vertex I is thus said to contain a loop.

**Degree of a vertex: **The number of edges that meet at this vertex. Also referred to as the order of a vertex. Vertices are referred to as either **even vertices** or **odd vertices** depending on this number. In the network graph K-O below, the degree of all vertices are as follows: K = 1; L = 2; M = 3; N = 1; O = 1.

**Subgraph:** When all edges and vertices of a network are comprised of some of the edges and vertices of another larger network. The network graph L-N below is a subgraph of the network K-O above. Vertices K and O and their connecting edges have just been removed.

**Simple graph: **Undirected, unweighted network containing no loops or multiple edges. Network graphs A-D, K-O, and L-N above are all simple graphs, whereas network graphs E-G and H-J are **not **simple graphs.

**Complete graph:** Simple networks whereby every vertex is connected to every other vertex by a single edge only. A complete graph with *n *vertices is denoted as *Kn. *Any simple graph with *n *vertices is a subgraph of the complete graph with *n *vertices: we add/delete edges to get from one to the other. The network graphs P-S and T-V below are both complete graphs as every pair of vertices share only a single edge (when a pair of vertices share a single edge, they are known as **adjacent vertices**).

You might have noticed in the network P-S above that there exists a junction in the middle of the network without the presence of a vertex. Imagine this as one edge going over the top of the other without interception, like a bridge crossing over a stream.

**Bipartite graph: **A network whose vertices can be divided into two groups whereby each edge connects a vertex from one group to a vertex from the other group. Vertices never share edges with those from the same group. Bipartite graphs do not have to be drawn with each group of vertices arranged in rows, but they normally are. The network graph below is a bipartite graph showing the relationships between two groups of vertices: W-Z (blue) and I-III (red).

**Undirected graph: **A network in which the relationships (edges) between vertices are of no directional significance. The network A-D below is an example of an undirected graph. Imagine that each vertex, A-D, represents a person, and each edge represents a hug. A hug is a mutual action - If person A has hugged person B, then person B has also hugged person A.

**Arc (directed edges):** Edges in which direction is important. These edges will usually have arrows to demonstrate its direction.

**Directed graph (digraph): **A network containing directed edges/arcs. They are used to model relationships between data in which direction is important. Note that in a digraph, not every edge must be a directed edge. If there is no arrow present on the edge, we can assume that direction is not significant for that particular edge. The network a-e below is an example of a directed graph.

Imagine that the network AA-EE above represents a group of five friends, and the information provided tells us which friends have visited whose houses. The network thus tells us that: person BB has visited person AA's house, but person AA has not visited person BB's house; but person BB and person CC have visited each other's houses. The same relationship is true for the rest of the edges depicted.

**Weighted graph: **A network in which each edge is worth a particular weight, and this tells us more information about the relationships between vertices. In the network diagram FF-JJ below, imagine each vertex is a town, and the edges are the distances between them in kilometres. These are called **weighted edges**.

**Connected graph:** A network is said to be connected if it is undirected and every vertex is connected to every other vertex by edges, regardless of length. The network K-O below is a connected network, as it is undirected and every vertex is connected to every other vertex by at least one edge.

**Disconnected graph:** On the contrary, a network is disconnected if there is at least one vertex sharing no edges with any other vertex. The network I-V below is a disconnected network, as there is no edge connecting vertex V to any other vertex.

# Traversability

Now, letâ€™s briefly look at the property of traversability. A network is traversable if it can be drawn in one go without taking your pen off the paper and without going over the same edge twice,Â although passing through the same vertex more than once is allowed.

Recall that vertices are regarded as either **odd** or **even** vertices depending on the number of edges connected to it. For a network to be traversable, it must be **connected** and have either **zero odd vertices** or **exactly two odd vertices.**

If a network has zero odd vertices: You can start at any vertex, and you will finish at that same vertex.

If a network has exactly two odd vertices: Your route must start at one odd vertex and will finish at the other odd vertex.

Consider network I-V above. Imagine it depicts a park, and the edges are short trails that you would like to walk. Is it possible to complete all of these trails without walking any of them twice?

To answer this, we must first consider the degrees of each vertex (i.e., how many edges are connected to that vertex). Vertices I, II and IV all have a degree of 2 and vertices III and V have a degree of 3. Therefore, network I-V can be said to contain three even vertices and **two odd vertices **and is considered** traversible**. However, this will only be possible if your route begins at either vertex III or vertex V and finishes at the other.