[MUSIC] So we talk about structural analytics tasks as broken down by this paper in 2012. What are some examples of traversal tasks? So one is to find the minimum spanning tree of a graph. And so that is the smallest subset of edges that connect the graph by some notion of connectivity. So if we ignore directionality we can talk about weakly connected graphs. So what is a minimum spanning tree of this graph? So we're looking for the smallest set of edges, a minimum spanning tree of this graph, because there might many that have the same number of edges. A minimum spanning tree of this graph. Well, we can get from a to b, and again we're gonna ignore directionality. There's actually two edges from A to B. So we take one of those. Then we get from b to f. And we get from b to e and we get from b to d, and then we get from d to c and e to g. And so that's one edge, two edge, three edge, four edge, five edge, six edge. And so the minimum span entry, the number of edges in the minimum spanning tree is six. Another way to get six is go from a to b and a to f and then the same otherwise, b to d, b to e, d to c and e to g. There's two different minimum spanning trees with the same number of edges in them. And there are fast algorithms to compute this that we're not necessarily gonna go into. This is a guided tour of various tasks you might want to compute but we're not actually gonna describe the algorithms in every case. Another traversal-oriented task is finding paths and circuits, and the classic example of this is Euler's Bridges of Konigsberg problem, where the task is to find a path where we visit every vertex and yet cross every bridge, in this graph here in the picture, only once. And so the observation that was made here is well if you enter by a bridge, you must also leave by a bridge. And you can't leave by the same one you came in on, because that's the definition of the problem. So this suggests that there needs to be an even number of bridges to every vertex, right, you have to have one to come in on and one to go out on. And then you can come back to this vertex as many times as you want. And so there's two sort of related results here. If you going from the bottom one here first, if you actually wanna start and end on the same vertex, well, the condition is that every vertex in the graph needs to have an even number of edges, so that you can come in by one, and you can leave by one. And this allows you to make an entire circuit all the way around the graph. If you don't care where you start and end, I'll just start on one and end on another, then it's a little bit softer condition, you can, most of the vertices need to have an even number of edges. But you can have, at most, two vertices that have an odd degree, the one you start on and the one you end on. Because then you'll need to leave by one, you'll need to come in by one. And I'm assuming undirected edges here. The definitions get slightly more complex if you talk about directed, but not much. Essentially you'd have a balance. You'd have the same number of in degree edges and out degree edges, okay? And so what's nice about this is a great result because it's very easy to check this condition, right? You can just add up the degrees of all the vertices in the graph and you can tell whether one of these circuits or one of these paths exist. But to sort of demonstrate the subtlety of some of these graph theoretic problems, you make a very slight change to the problem statement, the answer becomes a lot harder. So can we create a path that visits every vertex only once as opposed to every edge only once? Well, this is a hell of a lot harder. And the reason is intuitively if you think about it, every vertex has lots of edges, and so it's involved in lots of different paths, lots of different possible paths through the graph. And you're trying to find one of these such paths that touches every vertex only once. Well, given that this vertex is involved in lots of different paths, you're only allowed to use that vertex one time. And so, you can imagine that it's difficult to figure out what is the best way to use this vertex. There's a whole lot of different conditions you have to consider, okay? A related problem is, assume there's a cost to traversing each edge, right, there's a distance you have to travel, for example. Can we find the path that visits every vertex only once, but also has the minimum cost out of all these? And so there's no efficient algorithm that can exist for these problems. And so heuristics and approximations are the best we can do. This extension here is the traveling salesmen problem. These might be some of the tasks you might want to do. These actually come up, I would argue, less often in a big data context, especially this one, in part because it's such a difficult answer to compute and also it's not clear that it's all that useful, say, in a social network context, or in a web analytics context. You're not necessarily trying to find paths that touch every single vertex in the entire web. So this tends to be, the only times you're interested in touching every vertex in a graph I'll claim is when the graph is in some sense small, okay? So this is less of a big data problem but it's something to be familiar with if you're thinking about graph analytics. [MUSIC]