The day before the graph theory exam was a grey, cold, boring day spent at home. Originally I had imagined that I would make good use of this day, leisurely doing some more Altklausuren for graph theory and having some fun in the process. Afterall, this had been my favorite lecture this term. But somehow it didn’t work out that way. After three previous exams, I was already badly fed up with studying. And while graph theory certainly offers some of the most palpable and entertaining problems you will ever encounter in the wide realms of math, by that time I had seen more or less all of them. Moreover, going through the Altklausuren systematically, more and more of the problems started to look suspiciously familiar, even though I knew there were several exams I had definitely not done before. After a while I realized that our graph theory professor had a much smaller stock of exam questions and hence reused them much more extensively than I had thought. For instance, our mock exam was exactly the same as the mock exam three years earlier, which in turn was basically identical to an even earlier actual exam. And so it was with many of the questions. They recurred with an amazing regularity.
And with that discovery came the somewhat depressing realization that there were no new exciting problems to do for me on this last day. In fact, the problems I could do could be divided in two categories: Those that I had already mastered and done an nauseam, such as the Ford/Fulkerson algorithm for finding the maximum flow in a network, or insertion in an AVL (balanced binary) tree, both of which had so far figured in every exam, but which I hadn’t gotten wrong in the last dozen tries or so. They’re really very nearly fool-proof. And those that I had always tried to dodge, the nasty ones, which for me were three in particular this term–graph morphisms, graph grammars, and P/T nets. The latter two are simply modelling exercises, which can be quite involved when done right, but have of course in their favour the major benefit of any problem that involves modelling–that it’s hard to say exactly whether your model is right or wrong. So there is always a lot of leeway, for a benevolent professor, to give you most of the points for even trying. Still, both exercises are tricky and take a lot of time. And I just didn’t have the motivation any more for anything that involved, short of the actual exam. As for graph morphisms (is there a way to map one graph onto another so that any edge between two nodes in the original graph connects the images of the same nodes in the image), suffice it to say that the problem is NP-complete, i.e. you have to try every possible combination of nodes to find a solution. Seriously nothing you want to do by hand even for a small number of nodes. How could she ever expect us to?
Faced with the prospect of either torturing myself with problems I could, with luck, manage with a lot of time, but would probably botch under pressure regardless of how often I practised, or doing those in which I was already reasonably proficient again and again (and what for?), I ended up, maybe not surprisingly, doing neither. After a couple of hours I realized I was simply staring at the Altklausuren hoping in vain for something to turn up that I might usefully do. In the end I sarcastically resigned myself to making a system of it. For lack of any better idea, I would continue to stare, particularly at those problems I knew I had problems with, in the hope of committing the solutions to memory, either in case the same problems would in fact recur in the exam (which was not at all unlikely), or at least so I had a pattern for a solution that I might adapt to a new, but similar problem. Other than that, I would simply pray that at least not all three of my most hated problems would figure in the actual exam. With graph morphisms I would in any case be lost. A graph grammar or a P/T net I had a certain chance to fudge.
For the first time in this exam period I slept badly the night before the exam and had nightmares about failing (though not in this exam, but in others I had already taken). Very odd, considering that I had feared both operating systems and algorithms much more than graph theory. Maybe because this one was early in the morning, and in order to be my customary one hour early, we had to get up at 5 AM. In fact we were then so early that I had still time to bring our two older kids to school, we all riding our bicycles as we usually do, except this morning I was exceedingly nervous, fearing that a bike would break down or a tire go flat (the distance is about three miles with the kids, and than a couple without).
So many people were taking the exam (including a lot from higher semesters who had failed it earlier) that we had to write in two different rooms. That changed the setup just a bit. The professor would not be available for questions during the exam, since she could only be in one room at the same time and the rooms were not adjacent so that she and the other supervisor could not just exchange places. For the same reason, there would be no flexible additional time this time, as the two supervisors could not communicate during the exam. So we just got 100 minutes from start, instead of the usual 90 plus something in case most people were still writing when the time was up. And our usual “nobody hands in early” sermon that we had again preached over every available channel so to reach all who were taking the exam had been quite pointless.
The moment of truth was not quite a shock this time. In fact, skimming through the exam questions, I had a moment of sheer joy, because there was a graph morphism problem alright, but it was identical with the one from an earlier exam I had stared at for a long time just the day before, trying to make sense of it. What’s more, I could definitely remember the solution. So that was one problem out of the way, for almost certainly the full points. Other than that, the exam looked quite doable. Not very nice by any means, but not very nasty either. Though in addition to graph morphisms our professor had managed to sneak in both graph grammars and P/T nets by combining them in a single assignment–write a graph grammar that creates P/T nets!
The other problems were the usual 15 “true or false” tickboxes, though with quite a number of new questions (new to us, that is, as in they had not been in any previous exam we had access to); one shortest path problem using the A* algorithm (with heuristic values); one travelling salesman problem (find a shortest path that visits all nodes) that had also been in a previous exam; color a graph using a greedy and a breadth first algorithm, plus a small number of related questions; two proofs on graph complements; and what is the chromatic number (minimum number of colors) for a hypercube, i.e. a graph H(n) in which each node is a binary string of length n, and two nodes are connected when the strings are different in just one binary place. The example given was a H(2), which means a square with the nodes 00 – 01 – 11 – 10. Sadly though, there were none of the really easy problems that had so far figured in every exam and that we had practiced till we could do them in our sleep. No AVL trees. No flow algorithm either.
Still, I had no problem at all finishing in the assigned time. I did “true or false”, leaving open two questions on whether a graph whose adjancency matrix and incidence matrix are identical is planar or bipartite; I would have to think about these. I did the algorithms, which always means easy points, if you take the time to be careful. I had a few nervous minutes at this point, shaking hands and all, but overcame that fairly quickly and was quite on top of things for the rest of the exam. I really had fun figuring out the hypercube; my quick guess was that the number of colors was identical to the number of binary places in the strings, but then I sketched an H(4) (which is a stretch because logically it’s four-dimensional), and realized that the thing is bipartite, i.e. can be colored with just two colors, regardless of the size. Why? Well, because two binary strings that are different in one digit cannot be both different from a third in just one digit–it would have to be two digits for at least one of them, so there is no edge, hence no triangle, hence no three (or more) colors. Quite elegant.
As for the graph grammar for P/T nets, there was a lot of leeway in how to approach the problem. I simply decided (and said so) that a P/T net did not have to be connected and could have parallel transitions, but not parallel edges between a place and a transition. No idea whether that’s so or not, but for a modelling problem I think it’s important that my model is primarily consistent with my assumptions rather than strictly correct. So I quickly sketched a page and a half of rules, and that was that.
20 minutes left and I had done seven out of eight assignments, save for two “true or false” boxes. At this point it would have been no problem to just call it a day and still have a good shot at a very good grade.
But of course I didn’t. I looked at the second half of the remaining proof assignment and found that it was actually quite simple. Show that a graph has to be connected in order to be self-complementary, i.e. isomorphic to its own complement. It was easy to show the contraposition, that is, a graph that is not connected must necessarily have a connected complement and thus cannot be self-complementary. In fact, something very similar had been in a homework assignment quite recently. I am not quite sure what I wrote suffices as a proof, but there should be some points for it.
And so I had 15 minutes left and could give the first half of the same assignment a try. It looked quite cryptic at first, something with a subset of the nodes with a cardinality of 2, and I was unable to make sense of it. But then I concentrated on the last line, which said basically, show that for each node in a graph, the degree of the node plus the degree of the same node in the complement is equal to the number of nodes minus one. That’s actually completely self-evident, for the edges in a graph plus the edges in its complement, combined, are simply all possible edges between the nodes, so the combination of both graphs is a complete graph, in which of course the degree, i.e. the number of incident edges, for each node is the number of all nodes minus one–an edge to all other nodes. That’s easy to show, and quite possibly everything else in the assignment was just obfuscation. Unless I missed something.
I never figured out those last two “true or false” though. It’s hard to find a graph whose adjacency matrix and incidence matrix are identical in any case (besides, who uses incidence matrices?), and none of those I could find offered any hint as to a useful generalization about all of them being either bipartite or planar. In the end I just ticked “true” for both, working on the assumption that the chance was 50/50 either way, and that quite possibly at least one of those was a math professor’s trap, in the sense that formally the most absurd statement is true if the assumption is false.
Not since databases last term had I come of out of an exam with such a good feeling. Back then, I had simply known that I had at least 95 per cent of the answers correct and thus an almost certain A+. This time, I am at least sure that I have done all the problems and to the best of my knowledge haven’t seriously botched a single one. And unlike in databases, graph theory has the usual buffer, i.e. 100 out of 120 possible points are enough for an A+. If the professor grades reasonably kindly, and she usually does, an A should not be out of the question.
We went, the 15 or so in our core group, to the local pub as we have always done after the last exam in a term. This time, though, it felt moderately strange, since the exam was over at 10:30. So we spent a sunny winter day indoors, drinking alcoholic beverages well before the close of the day, which is something I haven’t done in a long time. There is a lot of the good old Protestant Ethic in me that says business before pleasure, and the day is for business rather than pleasure. But never mind. It was a good time, very relaxing, and we felt again like we had cleared a major hurdle.
For the third term is over. We have now reached halftime in our study program. And almost certainly this first half was the major effort. We have taken 15 exams already, and there are only 21 regular ones in this study program (not counting “compulsory choice” modules which often come with a presentation or project rather than an exam). In any case, almost all the basic, rote-learning, weeding-out courses are now behind us. The second half of the program will be a lot more about actually doing projects, programming a lot, specializing a little, finding our personal niche, and getting used to eventually doing a bachelor thesis and finding work somewhere in the industry. Or wherever else our way takes us. I feel we have already broken the back of this entire thing, and now the interesting part starts.
And of course, for me personally having even survived this third term is a small triumph. Not quite four months ago, I was seriously thinking about dropping out. Since then I have fought my way back and not only am I still here, but I’m going strong and will probably again finish all courses with good to excellent grades. In fact, just an hour ago the grades for algorithms came out, and true to form, our professor has once more managed to adjust the grading ceiling so dramatically that out of 64 people taking the exam, many of them for at least the second time, only 4 have failed. The grade average was just below a straight C, which is an amazing result, considering the length and difficulty of the exam. As for me personally, I got a not entirely unexpected, but still quite reassuring A+. I may make a mathematician yet!