## 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.

## Charlemagne – Pater Europae: New MOOC, new exhibition

Public attention across Europe these days seems to be directed towards the 100th anniversary of World War One. However, Europe’s roots reach back a lot further than that. This year also marks the 1200th year after the death of Charlemagne (748-814 AD). iversity commemorates the lasting influence of the emperor of the Kingdom of the Franks with a MOOC that starts today. The German city of Aachen, one of Charlemagne’s most important places of activity, hosts three major exhibitions about the man that is often referred to as “Pater Europae” – the father of Europe.

## The Empire of the Franks

In political terms, Charlemagne managed to establish a huge empire that stretched all the way from the Pyrenees to the Danube, and from Italy to the Baltic Sea. In doing so, he became the first post-antiquity emperor – with plenty of successors involved in bloody fights for the crown up until 1918, the end of the First World War, when four Empires (Germany, Russia, Austria-Hungary and the Ottoman Empire) collapsed almost simultaneously.

##### Image: Largest extension of Charlemagnes empire

What many people don’t know about the man also known as “Charles the Great” is that apart from his military conquests, he kept his empire together by establishing the “Carolinian educational reforms”. In the late 8th century, the common literacy level of Latin had deteriorated so badly that many priests were unable to interpret or even read the bible properly. In an attempt to counteract the looming loss of knowledge (which, as everyone knows, maintains close ties to power), he gathered the best and most renowned Latin scholars in his court.

## The roots of education

This included the scholar Alcuin, who created a curriculum and textbooks for Latin studies as well as the “seven liberal arts”: a blueprint for medieval education and a syllabus that consists of the so-called “Trivium”, the combination of grammar, dialectic, and rhetoric. In the eyes of Charlemagne’s contemporaries, this syllabus formed the basis of any critical thinking. With these as as starting point, students were then introduced into the “Quadrivium”, a second set of disciplines that encompassed mathematics, astronomy, geometry, and music.

Up until the late 18th century, generations of students in Europe were taught along those lines. Of course, during most of that time, education was a privilege of the few rich and the higher strata of society. Nevertheless, Charlemagne’s educational reforms also affected ordinary people’s lives, i.e. priests were better trained in Latin proficiency and bible studies. In effect, public thirst for education grew ever stronger and culminated in the foundation of the first universities less than 200 years after Charles the Great’s period.

To learn more about Charlemagne’s influence on European history, you have two great options: If you speak German, you can participate in the iversity MOOC “Karl der Große – Pater Europae?” offered by Prof. Rainer Leng from the German University of Würzburg, that deals with the aforementioned Carolinian educational reforms and other subject matter.

Secondly, regardless of what language you speak, you can visit the exhibition “Karl der Große – Macht. Kunst. Schätze” in Aachen, featuring original exhibits and documents from Charlemagne’s time. When opening the exhibition, German president Joachim Gauck had a clear opinion on Charlemagne’s impact: “That he’s called the father of Europe is still legitimate up to the present day.” Now he only has to convince the critical minds of Rainer Leng and his students.

## MOOCing: Lifelong Learning and Professional Education

I remember clearly the long car rides I spent with my grandparents as a child. They always featured ginger candy, strong perfume, and lectures on tape. Together, we learned about the French revolution, Impressionist art, and infectious diseases. Most of these university-level speeches were beyond my understanding, but I could see the value in continuing one’s education after formal schooling ends.

I’m currently a university student, so my learning is on-site and highly structured. But I don’t see my education ending the day I wear a cap and gown. Today’s technology has revolutionized the learning available to me. MOOCs engage masses past their college or high school years, enhancing careers and intellect. Participating in MOOCs facilitates lifelong learning, with experts in nearly all professional and scholarly interests, at the highest quality. Though lectures on tape have existed for years, MOOCs offer a more comprehensive learning experience with visual technology (link to article on MOOCs and visual technology), shorter segments, and engagement with other students and professors.

Massive Open Online Courses can include the most current content, and can be revised more quickly than traditional curricula to include today’s research. MOOCs can be taken individually or by entire teams of employees, ensuring that all are up-to-date in their skills and knowledge. MOOC value is not solely academic; they are helpful regardless of one’s degrees in expanding knowledge and skills.

iversity offers several courses that enhance careers, particularly in agriculture and finance. Given global food shortages, it is urgent that those involved in farming continue studying agriculture. In Internationales Agrarmanagement (International Agricultural Management), one learns how to plan and develop land environmentally and economically. Eastern Europe and Central Asia are plagued by outdated land management methods. This course could transform and improve the decisions of agricultural managers and workers, improving the efficiency and sustainability of land use.

Monte Carlo Methods in Finance could similarly improve your understanding of how the financial industry works, and your own investment decision. We are all aware that understanding risk became a prominent skill since the last financial crisis started in 2007. Those working in finance can brush up on their skills in risk management, understanding how it affects investment portfolios. Such learning could lead to better economic policy and wealth in the world’s leading nations. But one does not need to be a Wall Street banker, hedge fund manager, or professional in actuarial mathematics to get excited about this course. Whether you want to trade personal stocks or decode to predict the next bank crash, this MOOC teaches the principles of risk management.

MOOCs help one progress both professionally and personally, transforming how one continues to learn. We are no longer confined to long, auditory lectures, specific locations, or other’s schedules, even those of our grandparents. I look forward to exploring MOOCs with those all over the world already participating in these online courses. MOOCs are growing, covering more and more disciplines, from the technical to the artistic. There is a course for everyone; comment to share your favourite MOOCs.

by Anna Meixler

## Diversity in Science at Work: Goth Profs in Mathematics, the Beauty of Crystals and MOOCs to Change the World

iversity welcomes diversity. Our MOOCs are as varied as our topics and lecturers. Most professors do not wear goth clothing and stovepipe hats, but as MOOC Fellowship winner, mathematician Prof. Spannagel proves, professors with piercings exist. At least in Germany.

At the MOOC Kick-Off Workshop, we saw that iversity courses welcome many schools of thought, appealing to different types of students. Though they focus on specific subjects, these courses integrate sources and exercises from different fields, rendering lessons interdisciplinary in nature. These unique MOOCs allow one to explore design, mineralogy, and math through diverse lenses, generating new ideas about and approaches to scholarship.

The courses also vary linguistically. Some of iversity’s MOOCs launching this fall will be available not only in English but also in Russian and Spanish. Courses will also be in German, the former lingua franca of science. German remains preferable for students in countries like Poland and Ukraine, and has recently grown popular for younger graduates in Spain, Italy, and Greece amongst others due to the financial crisis.

The following are three of iversity’s outstanding German language MOOCs, whose diverse natures appeal to people of many backgrounds and interests.

Fascination with Crystals and Symmetry

Dr. Frank Hoffman combines ways of thinking in Faszination Kristalle und Symmetrie (Fascination with Crystals and Symmetry – this course will also be taught in English). He delves into crystallography and mineralogy, fields specific within chemistry—but his course is not narrow or only for the scientifically minded. Since Hoffman draws on philosophy, design, and morality, students confront ideas about beauty. Crystals are the avenue through which Hoffman teaches the structure and symmetry inherent in everyday life.

Mathematical Thinking

iversity’s mathematics course is also unconventional. In Mathe-MOOC: Mathematisch denken (Math MOOC: Mathematical Thinking) participants study arithmetic or geometry, or both. Prof. Spannagel is a nonconventional teacher. He even features the muppet Count von Count from “Sesame Street” in humorous videos to show “how mathematicians think, so students can solve problems by themselves.” Spannagel employs the “calculations of daily life that make people wonder. This course teaches students to experiment with numbers, finding methods to prove theories. We will start with everyday situations to help students formalize their approaches to math. We will reach the formal mathematical practice, not begin with it,” he said.

Changemaker MOOC: Social Entrepreneurship

Prof. Christoph Corves teaches how to solve social problems by approaching injustice with businesslike strategy, affecting longlasting change. Applying business methods to social projects, students learn how these two disciplines intersect and how to excel in project management. The training this MOOC provides is adaptable to any student project – from environmental concerns to social injustice, from education to nutrition and health. Course participants from all over the world learn how to create sustainable organisations to address their communities’ needs, in areas that interest them most. The course takes a multifaceted approach to social justice that transcends NGO structure, and teaches students to properly manage, budget, and strategize to make meaningful social impacts.

An iversity education is diverse. Our MOOC courses span from minerals to design, from math to anatomy. Within each course there is greater variety. With interdisciplinary sourcing and unconventional teaching styles, professors foster creative thought and welcome all types of students to their classes.

by Anna Meixler

## “Not Your Grandfather’s Greek History Class”: Talking MOOCs with Professor Andrew Szegedy-Maszak

Though MOOCs are offered in a wide range of disciplines, satisfying curious intellectuals and skill-seekers, most online courses exist in science, math, and technology. But organisations like iversity and institutions like Wesleyan University (the first liberal arts institution to launch MOOCs) are producing courses in the humanities as well. iversity spoke to Professor Andrew Szegedy-Maszak, Wesleyan’s first Distinguished Teaching Fellow, Jane A. Seney Professor of Greek and Professor of Classical Studies, whose MOOC “The Ancient Greeks” ran this fall and spring.

iversity: What was your personal approach to teaching a MOOC, and how might it differ from those instructing in science or math?

Szegedy-Maszak: With courses like organic chemistry or subatomic physics, what one needs to teach may be clear. But in a humanities course, there is greater flexibility in selecting topics, determining their depth, and assigning readings.

“I worked to allow for complexity, ambiguity, and ignorance”

Professor Andrew Szegedy-Maszak

(Courtesy of Olivia Drake)

I received advice for my course from Professor Peter T. Struck, Associate Professor of Classical Studies at the University of Pennsylvania, who taught a successful 10-week MOOC on Classic Mythology. He said he wished his course was shorter; I therefore made mine 7 weeks long. I did so for two reasons. The first constricted the effort involved in making the MOOC, which was hundreds of hours of prep. I also shortened my course to retain student interest. There is a downward slope in engagement from the first to last weeks of courses.

I gave 6 lectures per week, which cover the earliest Greek civilization to the death of Socrates. Deciding on these topics was, in some ways, arbitrary. I chose to teach a survey-style class. The Archaic Age, for example, receives scholarly attention. I could’ve done a course on just that period, or concentrated entirely on the Athenians. But I thought it’d be more useful to give students a broader historical perspective and introduce the sense of a wider Greek world. I taught what students are likely looking for, working in allusions to today’s research, because Greek history keeps changing. I wanted to suggest to my audience that I wasn’t teaching your grandfather’s Greek history class.

The origins of Greece: golden “Mask of Agamemnon”. Bronze Age.

National Archaeological Museum in Athens, Courtesy PD

iversity: Your MOOC assigns no papers, grades, or final assessment. How do you keep students engaged and focused? Is passion alone enough, and is it specific to humanities courses?

Szegedy-Maszak: For most students, Greek history is a subject they’re interested in and wanted to learn more about. I assign blunt, evaluative weekly questions to ensure they stay on track. These quizzes enable people who want them to get statements of accomplishment. Some students requested a tougher final examination, and a statement of accomplishment with distinction for those who do well on it. When the course is offered again on September 2, I may include a final to up the ante.

iversity: In your lectures, you don’t read from a script, as many MOOC instructors do.

Szegedy-Maszak: That’s similar to how I teach my classes at Wesleyan. I’ve been teaching this material for a long time, and know it well. I instead make a list of key topics to cover during each lecture. My MOOC doesn’t use textbook readings, also like my Wesleyan courses. All readings are primary sources in translation. The value of this particular subject [Greek history] lies in hearing the voices of long ago. It gives students a sense of what we, modern historians, deal with when reconstructing past narratives.

An unavoidable factor in teaching online is the amount of compression required, hitting only the subject’s high points. A friend said to “leave a lot out to get it all in,” my operating principle. My lectures at Wesleyan are 80 minutes, and these were from 12-20. Though I left a lot out, I felt a responsibility to the material and students not to dumb it down. I worked to allow for complexity, ambiguity, and ignorance, as there’s a lot we still don’t know about Greek history.

Bust of Socrates. His death concludes the MOOC.

Rome, Vatican Museum