First posted on Monday, April 28th. Updated Tuesday, April 29th. ------------------ Types of Questions ------------------ The math department mandates that a large chunk of our final exam will be multiple choice questions. With 7,000-9,000 undergraduates taking final exams in our department, we wouldn't be able to correct the exams and hand in grades unless machines did most of the work. You've already had a lot of Matching and True/False questions, and to some extent I can use those types of questions on the final -- "Mark (A) if the following statement is true, (B) if is is false." Even so, you'll have a lot of multiple choice questions on the final exam. To help you get used to that, I'm going to put at least one page of multiple choice questions on this test. Chapter 5 --------- * You should know the following terms, most of which are important for chpaters 6 and 7 as well: graph, vertex, edge, adjacent edjes, adjacent vertices, bridge, connected (and disconnected), degree, path, circuit, Euler path, Euler circuit, graph model, loop, multiple edges, eulerizing a graph, semi-eulerization. * You should be able to identify features of a graph, such as a loop, multiple edges, a bridge, a vertex of a certain degree, and so on. * You might be asked to make a graph model of a geographic area -- problems such as 19-22 in the Chapter 5 exercises. * You should know Euler's Theorems, particularly the first two. You should be able to identify when a graph has an Euler Circuit or Path. On a simple graph you may be asked to find such a circuit or path. * Using Fleury's Algorithm you should be able to find an Euler Circuit or Path. (This is a little different than the last point -- I might say, "Find _any_ Euler Circuit" or I might say, "Find an Euler Circuit starting at A using Fleury's Algorithm." If I say the second thing you really do need to use Fleury's Algorithm.) * You should know what both Eulerization and Semi-Eulerization mean, and be able to do it. (I won't give you terribly large graphs for these problems, I promise.) Chapter 6 --------- * You should know the following terms: complete graph, weighted graph, Hamilton Circuit, Hamilton Path, Traveling Salesman Problem (TSP). * You should know how many Hamilton Circuits a complete graph with N vertices has. * You should know the following algorithms for finding a Hamilton Circuit: Brute-Force, Nearest Neighbor, Repetetive Nearest Neighbor, Cheapest Link. You should know which ones are efficient and not-efficient (basically, they're all efficient except the Brute Force method) although I won't ask for a technical definition of "efficient." Chapter 7 --------- * You should know the following terms: tree, spanning subgraph (and spanning tree in particular), minimum spanning tree (MST), Steiner Point, Steiner Tree. * You should know what the four properties of a tree are. Pay special attention to the last two, because they're tricky -- be careful about that word "connected." * You should be able to find a spanning tree of a graph. If it's a weighted graph, you should be able to find the minimum spanning tree using Kruskal's Algorithm. * You should know what the shortest distance between 3 point is -- either the MST or the corners linked to an interior Steiner Point, depending on how big the angles are. In particular, you should know when you can or can't fit a Steiner Point inside. (It has to do with 120.) * You may be presented with a few simple examples of shortest networks with more than three points. As discussed in class, there is no general solution, but you should know what facts we do have. For example, if we can't add new interior points, then the the shortest network is the minimum spanning tree (MST). If we _can_ add new points, it's either the MST or a network with new interior points, each of which must be a Steiner Point. (In other words, it's either the MST or a Steiner Tree.) * You should know why the number 13.4% is important. Happy Studying!