Hi, everyone. This week, we'll study purposes of graph classes. We'll study trees, bipartite graphs, and planner graphs. Let's start with trees. And here's the first problem. The hurricane Barbara destroyed all roads in a country, and we want to restore some of those roads so that every city is reachable from any other city. So I can get from every city to every other one possibly going through some other cities. On every road, you see there is repair cost. And I want to find the cheapest way to make this country connected again. In this first example, I need to choose some roads. Can I choose two roads? No, there are four cities. I cannot connect them just by two roads. So probably, I need three roads. And if I take three shortest, three cheapest roads, then they do the jobs, they connect all four cities. This means the minimum repair cost in this problem is 5, the cost of 3 cheapest roads. Here is another example. There are seven cities so to make it connected, I need at least six roads. Let's try again to choose the cheapest roads. I can take this road of cost 1 or the roads of cost 2, but still I need one more road. Currently I have two connected components, the orange one and the blue one, and they're not connected with each other. I can't get from B to D, for example. So I need to connect the blue connected component with the orange one. How do I do this? I can, for example, take this edge of weight 4, of the cost 4. And this would work, this would give me a plan which cost 13. Can I find a cheaper plan? I took 5 cheapest roads and ended at a road of cost 4. In order to beat me, you have to take 5 cheapest roads and the road of cost 3. But it is easy to see that those combinations don't work. If you take this road away, of cost 3, it doesn't connect the blue and the orange components. If you take this one, it doesn't connect either. So by far the cheapest way, the cheapest repair plan here costs 13. And here is one more example. Again, I suggest use the following algorithm. Let's just be taking cheapest edges, as long as they're useful. As long as they connect some vertices which haven't been connected yet. For example, first I take this edge of cost 1. Now, I take this edge of cost 2. Should I take this edge of cost 3? No, it just connects B with C but they're already connected through the vertex G. So let's not take it, it's useless. Okay, now it can take this edge of cost 3, and this one of cost 3. This one of cost 4, again, it's useless. A and F are already connected through B and G, so I don't take it. I can take this one of cost 4 because it takes connects D with E. And this one of cost 4, and I'm done. This is solution, and actually this is an optimal solution. And we will prove later this ordering always gives an optimal solution.