Thank you for joining me on the closing part of our course. My name is Ilia Stepanov. In this module, we will learn basic definitions and algorithms of graph theory in regard to competitive programming in general. This theory has a number of replications in practice, so the entire topic is very useful and important. Let's begin. The basic element of graph theory is the graphs that are represented by vertices and edges. A vertex may generally stand for an object of any nature. In different situations, vertices can correspond to people, cities, houses, or even countries. A lot of real life models that somehow include relationships between several objects can be represented with the graph. The vertices of this graph will stand for the objects that have relationships among them. In the left half of the slide, the vertices correspond to John, Pete, and Mary. In the right half, they correspond to Paris and Moscow. The links between the vertices are presented via edges. For example, talking about students, a friendship between two people can be represented by an edge. If people are drawn as points or circles on a plane, the edge can be naturally shown as a segment or an arc connecting the points of two friends. In the left picture, Pete does not know Mary, while John knows both of them. While discussing cities and road maps, an edge can represent a road between the cities. Once again, if objects are drawn as points, then a line between two points can indicate a highway between these two cities. The absence of an edge indicates the absence of the corresponding highway. In the right picture, the single edge stands for a road between Paris and Moscow. Formally, a graph is a pair of sets. The first one represents the set of vertices and the second one represents the set of edges between some pairs of these vertices. Now let's focus on the example with the road map between cities. Let's say that the edge between the cities denotes the existence of a road between them. It is quite natural to ask oneself, is it possible to travel from city U to city V? It is one of the questions that appear in practice. Indeed, sometimes it is required to establish whether one can travel from one city to another by car, and if one can do without buying a ticket for a train or a plane. Here we may introduce the notion of connectivity. We will be saying that vertex V is reachable from vertex U if a path exists via the edges starting at U and terminating at V. We can travel by car from U to V without having to fly or teleport. The given graph has vertices A through G, and one can travel from A to B, but not from A to D. A connected component in a graph is an inclusion-wise maximal set of vertices such that any two vertices of the set are reachable from one another. For example, here A, B, and C form a connected component, while D and E don't. This is due to the fact that D and E can be joined by F and G. This is what we mean when saying inclusion-wise maximal. One can easily see that any graph can be represented as a union of several completely independent connected components. It is possible to travel between any pair of vertices in each component, but there is no way to pass from one component to another. What do you think? How many components does this graph have? There are two of them. The first one contains vertices A through C, and the second one contain vertices D through G. Moving on, a graph is connected if it has a single connected component. In other words, one can travel between any pair of vertices. Thus, the given graph is not connected. We can notice that the given mathematical definition of connectivity is in perfect agreement with the natural perception of the notion connected road map. All these definitions will be extremely necessary in operation of any logistic company having to do with cargo delivery. They are bound to determine if the graph of cities is connected or they'll have to resort to air transportation means. Continuing the description of the road map model, it makes sense to discuss the notion of a weighted graph. In such a graph, every edge is given not only by its endpoints, but also its weight. In the road map graph, the weight of an edge may correspond to to the length, say in miles of a road between the cities. Let's ask ourselves a question. Which of the graphs on the slide is weighted? In fact, that is only the second one, where every edge is marked with its own weight. In the first graph, however, the weight of an edge between A and B is not clearly defined and it stops us from saying weighted in relation to this graph. Another wonderful definition in graph theory is the notion of a tree. The easiest definition goes this way. A tree is a connected graph in which the number of vertices exceeds the number of edges by one. I suggest you determine which of the graph is a tree. I'm sure you have already guessed that only the left one is a tree. Indeed, it has five vertices and four edges. The right graph, however, has six vertices and five edges, so the property of the numbers of vertices and edges is fulfilled. Nevertheless, the right graph is not connected, so it is not a tree. It is widely known, a tree has the following additional properties. First of all, it has no cycles. It means that an arbitrary itinerary cannot come back to the starting point if it does not use the same edges more than once. The right graph, for example, has a cycle of length three. Secondly, if a graph is a tree, then a single simple path exists between every pair of vertices. You can convince yourself in this with the help of the left graph. The understanding of which graph is a tree and which isn't will help us in further algorithms. Furthermore, trees are the simplest form of graphs. They don't have any cycles, and many combinatorial problems can be solved using trees much easier than using arbitrary graphs. The same goes for real life applications. If a network is represented with a tree, some genuinely hard problems can be solved easily with some basic algorithm. Now let's turn to the notion of directed graphs. In previous models, all the graphs we're undirected. Indeed, friendship was assumed to be mutual and roads between cities were bidirectional. That is why, if John is Pete's friend then Pete is John's friends to, and a straight road from A to B means that the road from B to A exists as well. However, sometimes directed graphs do arise. For example, does a person really remember another person? Let's say John is a world-class celebrity, then he cannot memorize all of his fans. But James, as his most loyal admirer, will never forget John. This is the reason to draw a directed edge from James to John, meaning that one remembers the other, but not vice-versa. Formally, a directed edge is an ordered pair of vertices from two. Directed edges on the map can correspond to unidirectional roads. A more applicable case here would be a map of intersections and streets in a big city. Many of the passages can be unidirectional only, meaning that cars can use this road only in one direction. If one introduces a graph with vertices corresponding to the intersections and with edges corresponding to the streets, one can also raise a question of finding the shortest distance between two intersections. Indeed, you may already be late for an important meeting but the center of the city is generally designed for pedestrians rather than cars. Many streets will be unidirectional. This mathematical model allows you to formalize the problem strictly and clearly, as well as to use classical algorithms for solving it. Today we have learned a few basic concepts of graph theory. We have found out the definition of a graph consisting of vertices and edges. With the help of the notion of reachability between vertices, we have defined connected components, and we have also defined a connected graph. We've seen a natural example of a weighted graph, and we've also discussed several applications of the theory. We've learned what a tree is, and we've established the difference between directed and undirected graphs. Our next tutorial will be devoted to the means of graph representations in computer memory for its convenient use. We will also discuss the algorithms of converting this means one to another.