Mini-Project #1

Part I: Computer Representation of Graph

Part 1 comes directly from the textbook on page 173.

In many real-life routing problems, we have to deal with very large graphs - a graph could have thousands of vertices and tens of thousands of edges.  In these cases, algorithms are done by computer.  Unlike humans, computers are not very good at interpreting pictures, so the first step in using computers to perform computations with graphs is to describe the graph in a way the computer can understand.  The two most common ways to do so are by means of matrices.  

In the first part of this project, you are asked to write a short research paper describing the use of matrices to represent graphs.  Explain

1. what is a matrix,
2. what is an adjacency matrix of a graph, and 
3. what is the incidence matrix of a graph.

Illustrate some of the graph concepts that you know and understand (degrees, multiple edges, loops) in matrix terms.  Include plenty of examples.  You can find definitions and information on adjacency and incidence matrices of graphs in many graph theory books.  

Part II: Modeling the Spread of Ebola

Part II is about connecting our knowledge from the book, with our goal for modeling the spread of Ebola.  

Create a graph consisting of five cities within West Africa and five cities outside of West Africa where Ebola might be transmitted.  Describe what you think might be likely sources of travel between the various cities and represent these connections as a single edge linking the two cities.  Assign weights to each of the edges where a larger number indicates a stronger likelihood of transmission and clearly communicate what your assigned weights represent.  Use both a graphical and matrix to represent your graph.  

Consider referencing http://rocs.hu-berlin.de/projects/ebola Links to an external site. or http://rocs.hu-berlin.de/D3/ebola Links to an external site. for information and suggestions.