[MUSIC]. 
So, we talked 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, notion of connectivity. 
So if we ignore directionality, we can 
talk about weakly connected graphs. 
So what is the minimum spanning tree of 
this graph? 
So we're looking for the smallest set of 
edges. 
A minimum spanning tree of this graph, 
cause there might be many that have the 
same number of edges in them. 
A minimum spanning tree of this graph. 
Well, we can get from a to b, and again 
we're going to ignore directionality, so 
there's actually two edges from a to b. 
So we take one of those. 
Then we can get from b to f, then we can 
from b to e, and we get from b to d, 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 spanning tree, 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. 
Okay. 
So there's two different minimum spanning 
trees with the same number of edges in 
them, and there are fast algorithms to 
compute this, so we're not initially 
going to go into. 
This is sort of a guided tour of various 
tasks you might want to compute, but 
we're not necessarily going to describe 
the algorithms in every case. 
Right? 
So another traversal oriented task is, 
finding paths and circuits. 
And so the, you know, classic example of 
this is Euler's Bridges of Konigsberg 
problem, where the task is to find a, 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 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, you have to have one to come in on, 
and one to go out on. 
And then you can come back, 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 want to start in 
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, the 
graph. 
If you don't care where you start and 
end, your I'll just start on one and end 
on another then its a little bit softer 
condition. 
And 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 you'll need to leave by one 
and you only need to come in by one. 
And, I'm assuming non-directed edges 
here. 
The definitions get slightly more complex 
if you start talking about directive but 
not, not much. 
Essentially you'd have a balance, you can 
have the same number of in degree edges 
and out degree edges, okay. 
And what's nice about this is it's a 
very, very, you know. 
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, whether one of these 
circuits or one of these paths exists. 
But, to sort of demonstrate the subtlety 
of you know, some of these graph 
theoretic problems, you can 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 is that intuitively, if you 
think about it, you know, 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, you, you there's 
vertexes 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, have to consider, 
okay. 
A related problem is, you know, assume 
there's a cost to traversing each edge. 
Alright, there's a distance you have to 
travel, for example. 
Can we find a 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. 
And this, this extension here is the, you 
know, traveling salesman problem. 
Okay. 
So these might be some of the al tasks 
you might want to do. 
These actually come up, I would argue, 
less often in a big data context. 
Pers, 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 is, this tends to be, you know, 
the only times when you're interested in 
touching every vertex in a graph, how 
clean, 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, 
in, in, if you're thinking about graph 
analytics. 
Alright. 
So one more traversal task, just to be 
familiar with, is maximum flow problems. 
So here the input is a graph with labeled 
edges indicating the capacity of each 
edge, and then special vertices sources 
and sinks, and the idea is to find a sub 
graph that maximizes flow between sources 
and sinks. 
And so, the observation here is that for 
each vertex, incoming flow must equal 
outgoing flow. 
Okay. 
And so in this example, if a is a source, 
and f, f and g are the sinks, then you 
can think about. 
A sub-graph where you just have a 
directly to f because it's only one hop 
away, and so the flow between them is 
two, but if you look at a path a to b and 
then b to f, you get the flow of four 
here and the flow from, or the capacity 
of four here and the capacity of three 
here which means the maximum flow along 
this is three. 
Right, there's some unused capacity on, 
on this edge, but three is still higher 
than two, and so that's, we want to 
include that in the, in the sub-graph 
from, from a to f. 
Okay, and then get over to g, you can do 
sort of a similar walk and say, well, one 
path is b to d. 
Through a capacity of five, and d to e 
through a capacity of two, and e through 
g through a capacity of two. 
And so the maximum flow here is two. 
While a to b, b to d, d to c and c to g, 
the maximum capacity is three. 
This edge is the, is the, is the weak 
link. 
Okay, so it looks like the max flow 
sub-graph is a, b, f, d, c, g. 
Or rather, d, i, g, b. 
The edge b, d. 
The edge d, c. 
And the edge c, g. 
And the edge b, f.