DescriptionThe aim of this project is to learn as much as possible about various computational aspects of graphs and networks. Graphs and networks are discrete structures consisting of vertices (nodes) and edges (bonds). Edges can have directions or not. Sometimes the vertices and edges come with weights, for example if the vertices represent cities then their weights could be the population of the cities; the edges could represent roads connecting the cities, in which case the weight of the edges could be the length of the road connecting cities; if the network represents a system of waterpipes, the weights on the edges could be the capacity of water that can flow through these waterpipes. These are just some examples to illustrate the need of these extra structures associated to a network.At the start of the project, you will consider various possibilities of implementing these discrete structures in Python (or a similar programming language) and then create the relevant basic programming tools. Directed edges between nodes could be represented via pointers or the graph could be represented via its adjacency or incidence matrix. Different representations might be more or less useful when we implement specific graph algorithms. Once these basic software tools are available, we will discuss various related concepts like connectedness, shortest paths, distances, spanning trees, matchings, ... and also fundamental questions in graphs and networks like flows, planarity, colourings, existence of Hamiltonian cycles, ... The lists of these additional concepts and structures could be endlessly continued. You will then implement algorithms solving particular problems arising in connection with these additional structures, investigate their efficiency and compare different algorithmic solutions for the same problems. The concrete computer realisations of a graph can be very relevant for the efficiency of a particular graph algorithm. On the one hand, this project offers a high degree of experimentation, it requires creativity and willingness to ''make your hands dirty'' by implementation and testing. On the other hand, there are tremendous opportunities to investigate the algorithmic side theoretically by understanding various ways to measure and compare the efficiency of algorithms: Do the algorithms solve a problem in polynomial and exponential time depending on the size of the graph? Even if an algorithm is of polynomial order, is it really fast enough to solve naturally appearing practical problems? Is the problem NP-hard or NP-complete? There is no limit to investigate these and other fundamental questions. This theoretical research area is called Complexity Theory. Below are some books which might be useful for this project. There are, of course, many more sources to be found via the internet, in bookstores, and in libraries. As you can imagine from the description of this project, good programming skills are an essential requirement if you decide to choose this topic. Some Resources
email: N Peyerimhoff |