It will not come as a surprise that graphs are used heavily in order to analyze networks. In this module, we will introduce some examples and show how the various properties of graphs that were introduced in the previous sub-module and some of the algorithms that we will introduce can be used to determine properties of networks that are relevant to some applications.
Connectedness - Graphs, perhaps not surprisingly, can prove extremely useful as a tool to analyze computer networks. A good computer network is a connected graph. Given a set of network nodes and connections, which we can obviously analyze as a set of vertices and edges, a useful algorithm would be one that can quickly determine which the graph is connected.
There are different ways in which we can determine whether a graph is connected. One is through search: We can start at an arbitrary vertex, use a graph search algorithm, and count all the vertices we can reach. If the number of vertices we can reach is equal to the number of vertices in the graph, then the graph is connected. There are different graph search algorithms. Two that are particularly useful are breadth-first and depth-first search. Find out more about breadth first and depth first search, and use the dropbox "Graph Search" to show the order in which you would visit the vertices in the graph below, starting at vertex v4.
Adjancency graphs are also useful tool to determine whether a graph is connected. In order to show you how this works, recall that an adjacency matrix is esentially a 2-dimensional array both of whose dimensions are the same size. We will call this the size dimension of the array.
So, to determine whether a graph is connected from its adjacency graph M, we can use the following algorithm:
copy M into a new graph M';
changed = 1;
while (changed == 1) {
changed = 0;
for (i = 0; i < size dimension of M'; i++) {
for(j = 0; j < size dimension of M'; j++) {
if (M'[i,j] = 1) {
for(k = 0; k > size dimension of M', k++) {
if (M'[j,k] == 1 && M'[i,k] != 1) {
M'[i,k] = 1;
changed = 1;
}
}
}
}
}
}
If M' now completely consists of 1, G is connected.
Perform the following three tasks:
Upload the results to the dropbox called "Adjacency Matrices".