Maximal matchings are a useful tool for

getting a coarsened graph. All we need now is

an algorithm to compute one. Let me describe a simple scheme

to you based on randomization. At each step of this scheme, you’ll

choose any unmatched vertex at random. So initially, no edges are matched,

so let’s pick any vertex. How about this one? Next, you’ll match this vertex to

one of it’s unmatched neighbors. Again, since we’re just starting,

all of the neighbors are unmatched. So how do we pick one? Well, there are lots of strategies. For example,

you could just pick one at random. A different approach is something

called a heavy edge matching strategy. So heavy. So heavy. The idea is to look at the unmatched

edge with the highest weight and then choose it. For instance,

suppose these are the edge weights. Then among the two unmatched neighbors,

this edge has the higher edge weight, two versus one. So you’d choose it. But why is the heavy edge

matching strategy a good one? In fact, there’s not a whole lot of

definitive rigorous analysis out there. But there is a lot of

experimental evidence. What I want to do now is just

give you some informal intuition. Consider some graph Gi. Suppose we were to

match these two edges. Contracting them would

yield a course in graph. Let’s call it Gi + 1. Note the edge weight of two that

connects the two super vertices. Now, if you were to sum the edge weights

in the original graph, you’d get 12. That’s because there are 12

edges each of unit weight. Here let me use the notation X of some object to count the number

of edges in that object. Now the sum of the weights

on the final graph is 10. This is just the total edge weight of

the original graph minus the edge weight of the matched edges. Here, let Mi denote the matching. Now, the strategy of

selecting heavy edges will tend to try to increase this factor. And if this factor is bigger,

then this factor will be smaller. In other words, the heavy edge

heuristic is really about increasing this term in order to decrease the

overall edge weight in the next graph. The heuristic idea is that

the smaller this term is, the more likely it is that all

the edges you’ll cut will be small. Again, this is clearly

not a rigorous proof. In fact,

there are a ton of other heuristics. But most of the evidence is empirical. Anyway, if this is a topic of interest

to you, head to the instructors notes or the class forum for pointers to papers that will discuss

all these issues in a lot of detail.

"soo heavyyy" – I cringed into a black hole. Otherwise, good video