《Transcript16.docx》由会员分享，可在线阅读，更多相关《Transcript16.docx（13页珍藏版）》请在金锄头文库上搜索。
1、Video Lectures - Lecture 16 Topics covered:Greedy Algorithms, Minimum Spanning TreesInstructors:Prof. Erik DemaineProf. Charles LeisersonTranscript - Lecture 16- valuable experience. OK, today were going to start talking about a particular class of algorithms called greedy algorithms. But were going
2、 to do it in the context of graphs. So, I want to review a little bit about graphs, which mostly you can find in the textbook in appendix B. And so, if you havent reviewed in appendix B recently, please sit down and review appendix B. It will pay off especially during our take-home quiz. So, just re
3、minder, a digraph, whats a digraph? Whats that short for? Directed graph, OK? Directed graph, G equals (V,E), OK, has a set, V, of vertices.And, I always get people telling me that I have one vertice. The singular is not vertice; it is vertex, OK? The plural is vertices. The singular is vertex. Its
4、one of those weird English words. Its probably originally like French or something, right? I dont know. OK, anyway, and we have a set, E, which is a subset of V cross V of edges. So thats a digraph. And undirected graph, E contains unordered pairs.OK, and, sorry? Its Latin, OK, so its probably prett
5、y old, then, in English. I guess the vertex would be a little bit of a giveaway that maybe it wasnt French. It started to be used in 1570, OK. OK, good, OK, so the number of edges is, whether its directed or undirected, is O of what? V2, good. OK, and one of the conventions that will have when were
6、dealing, once we get into graphs, we deal a lot with sets. We generally drop the vertical bar notation within Os just because its applied. It just makes it messier. So, once again, another abuse of notation. It really should be order the size of V2, but it just messes up, I mean, its just more stuff
7、 to write down. And, youre multiplying these things, and all those vertical bars.Since they dont even have a sense to the vertical bar, it gets messy. So, we just drop the vertical bars there when its in asymptotic notation. So, E is order V2 when its a set of pairs, because if its a set of pairs, i
8、ts at most n choose two, which is where its at most n2 over 2, here it could be, at most, sorry, V2 over 2, here its at most V2. And then, another property that sometimes comes up is if the G is connected, we have another bound, implies that the size of E is at least the size of V minus one. OK, so
9、if its connected, meaning, what does it mean to have a graph thats connected?Yeah, theres a path from any vertex to any other vertex in the graph. Thats what it means to be connected. So if thats the case, that a number of edges is at least the number of vertices minus one, OK? And so, what that say
10、s, so one of the things well get into, a fact that I just wanted to remind you, is that in that case, if I look at log E, OK, log of the number of edges, that is O of log V.And by this, is omega of log V. So, its equal to theta of log V. OK, so basically the number of, in the case of a connected gra
11、ph, the number of edges, and the number of vertices are polynomially related. So, their logs are comparable. OK, so thats helpful just to know because sometimes I just get questions later on where people will say, oh, you showed it was log E but you didnt show it was log V. And I could point out tha
12、t its the same thing. OK, so theres various ways of representing graphs in computers, and Im just going to cover a couple of the important ones.Theres actually more. Well see some more. So, the simplest one is whats called an adjacency matrix. An adjacency matrix of the graph, G, equals (V,E), where
13、, for simplicity, Ill let V be the set of integers from one up to n, OK, is the n by n matrix A given by the ij-th at the entry is simply one if the edge, ij, is in the edge set and zero if ij is not in the edge set. OK, so its simply the matrix where you say, the ij entry is one if its in the matri
14、x. So, this is, in some sense, giving you the predicate for, is there an edge from i to j?OK, remember, predicate is Boolean formula that is either zero or one, and in this case, youre saying its one if there is an edge from i to j and zero otherwise. OK, sometimes you have edge weighted graphs, and
15、 then sometimes what people will do is replace this by edge weights. OK, it will be the weight of the edge from i to j. So, lets just do an example of that just to make sure that our intuition corresponds to our mathematical definitions. So, heres an example graph. Lets say thats our graph.So lets j
16、ust draw the adjacency the matrix. OK, so what this says: is theres an edge from one to one? And the answer is no. Is there an edge from one to two? Yes. Is there an edge from one to three here? Yep. Is there an edge for one to four? No. Is there an edge from two until one? No. Two to two? No. Two to three? Yes. Two to four? No. No edges going out of three. Edge from four to three, and thats it. Thats the
