## Introduction to Graph Theory

«Poor, sad-eyed stranger!» – this is how American author Mark Twain described the canvasser or the salesman. Why was he so sad and poor? Maybe because he had to solve the big problem of a travelling salesperson – “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”. Without the answer, we could not trade today.

A long time ago, this was an inconvenient difficulty not only for the canvasser, but also for the mathematicians. The travelling salesman problem was mathematically formulated in the 1800s by the Irish mathematician W.R. Hamilton and by the British mathematician Thomas Kirkman.

Up to this day, the issue is existent for postmen and travellers all over the world. The most convenient and profitable approach for a solution is graph theory.

Another issue is called the Seven Bridges of Königsberg, named by Leonard Euler in 1736, and it sounds more like a beautiful legend than a problem.

Königsberg in Prussia (now Kaliningrad, Russia), was set on both sides of the Pregel River, and included two large islands, which were connected to the rest of the city by seven bridges. The problem was to devise a walk through the city that would cross each of those bridges once and only once. The residents of the city always challenged visitors and travellers to see whether they could solve the problem. However, no one except Leonard Euler could find a way; not even the locals. Euler proved that the problem had no solution. He was able to find a rule, using which, it was easy to determine whether it is possible to pass through all bridges, without passing twice on either of them. Its negative resolution laid the foundations of graph theory. Euler wrote a paper about the The Seven Bridges of Königsberg and published it in 1736. It was the first paper about graph theory in history and the first page of the history of graph theory.

This is the history. Now, let’s take a look at pop culture. Labyrinths have featured prominently in pop culture for a long time. Starting from the myths of Theseus and Minotaur and ending with the dystopian science fiction action thriller “The Maze Runner”. Or do you remember the fourth movie about Harry Potter and his adventures in the labyrinth? And the “The Shining” by Stephen King? The labyrinth challenges the hero to find the right path to escape. The study of labyrinths is also connected to graph theory. If the protagonists knew the basics of graph theory, they might have found a faster way out in some cases.

What then is the graph theory?

Graph theory in mathematics means the study of graphs. Graphs are one of the prime objects of study in discrete mathematics. In general, a graph is represented as a set of vertices (nodes or points) connected by edges (arcs or line). Graphs are therefore mathematical structures used to model pairwise relations between objects. They are found on road maps, constellations, when constructing schemes and drawings. Graphs underlie many computer programs that make modern communication and technological processes possible. They contribute to the development of thinking, both logical and abstract. For example, maybe you remember this game from your childhood: connect the dots on the piece of paper to make a figure, a dog or a cat – those connections are also graphs.

We all know the saying: “Mathematics is not needed in real life”, but graph theory is actually applicable in real life. In fact, this is how it was discovered.

ITMO University in St. Petersburg, Russia, is a large state university and one of Russia’s National Research Universities. Research priorities of the university are concentrated on information and photonic technologies. The online course „Einführung in die Graphentheorie“ is focused on the study of methods and algorithms of graph theory and their application in practice. The goal of the course is to develop basic knowledge and skills to solve the most important and frequently encountered graph problems.

You will, first of all, gain a readiness to demonstrate a basic knowledge of mathematics (graph theory). And secondly, you will learn to apply effective methods and algorithms for solving typical graph problems in practice. Furthermore, this course will be very useful for all those, who encounter graph theory in university – either on a beginner level or for in-depth studies and research.

The course consists of four chapters and a final exam. The theory will be taught through video lectures. The length of our teaching videos is of the time it would take to teach the same material in a lecture setting. Therefore, each video lecture lasts about 15 minutes. After completion of each video lecture, an online quiz is conducted to verify the that you as a learner understand what has been taught.

The main goal of this course is to gain basic knowledge in graph theory. This knowledge will help you to independently study other sections of graph theory in the future, and to apply it in real life. Do note, however, Graph theory develops very quickly. There are various terms and concepts, the correct use of which is possible only in the context of the problem being solved.

## SMART-MOOC for Tanzania

For most visitors the African country of Tanzania means wildlife. Range Rovers, packed with tourists, guides and drivers, the latter often students from Dar es Salaam, gather in endless queues at the entrance of Ngorongoro with its rhinos, lions and elephants. Some tourists visit the historical Stone Town on the island of Zanzibar afterwards or combine dolphin watching with a taste of Mvita Ali’s incredible seafood buffet on a sandbank at Kizimkazi.

But virtually no one takes much time to voluntarily visit Dar es Salaam, Tanzania’s busy trade hub at the coast with its 3 or maybe 4 million inhabitants. The port city is big, loud and not exactly the most beautiful harbor town at the Indian Ocean. While most tourists avoid the city, businessmen do not. A lot of European, American and especially Chinese companies are located in Dar es Salaam. Entrepreneurs from India and the Middle East add to the business community. Banking and financial services like micro-finance, mobile communication, logistics and other businesses thrive and grow comparably much faster than in Europe and even many parts of Asia.

Dar es Salaam: not enough software engineers

The bottleneck for this growth is education. A lack of technically skilled workers leads to open positions across corporations in Tanzania. Without more graduates, degree holders and skilled specialists for IT, risk management or actuarial science, the economical capital of Tanzania can’t compete with the West, China or other African nations like Kenya, Nigeria and South Africa.

Dar es Salaam houses seven universities, among them the Open University of Tanzania and the International Medical and Technological University. The quality of these universities is under dispute though. Even the best one, the University of Dar es Salaam ranks among the worst universities worldwide in terms of research and scientific excellence. As well, these universities do not offer enough study courses in Information and communications technology (ICT) that are in high demand now. And higher education at a university is not available for everyone in a country that is as poor as Tanzania.

Internet connections in Tanzania are comparably good though, given that Dar es Salaam is a landing point of the submarine high-speed Seacom cable, connecting it directly with Mumbai and Marseille.

So, one plausible approach to tackle the issue of higher education is by MOOCs. That is why the World Bank sets up pilot projects for IT and ICT education in Sub-Sahara Africa as a part of their “New Economy Skills for Africa Program – ICT” or short: NESAP-ICT.

In Tanzania, the World Bank designated Dar es Salam as a knowledge hub for SMART skills – SMART being an abbreviation for Software, Mobile Applications, Research and Technology. The next step was to define the critical success factors for a MOOC about IT in Tanzania, like a real impact on employment chances or the need to get credits.

MOOCs are possible: Seacom Cable

(here: undersea near Zanzibar) supplies Tanzania with high speed internet

The Washington-based World Bank choose an American company, Coursera, as its partner, not a MOOC-provider from the EMEA-region like iversity. Together with its partner, the World Bank will design the MOOC over the summer of 2013.  Starting MOOCs in East-Africa might have another preferable effect: stopping the brain-drain from Tanzanian students to Europe and America, where they often stay after graduation.

What the World Bank's EduTech blog article about MOOCs in Afrrica does not mention: the opportunity to take courses outside the “knowledge hub”, to take part in a MOOC anywhere in Tanzania. A huge advantage in a country where many of the most gifted young women and men work at least part-time or for some months outside the commercial capital in the tourism regions to make a living. Especially in a country like Tanzania it makes sense to reach out for prospective students where they are today, not where universities are located for historical reasons. Thus MOOCs can make a difference in developing Tanzania’s economic future.