WIXLIB

3–2ChemistryAlkanes have chemical formula Cn H2n 2 . The first four (n 1, . . . 4) are methane, ethane,propane and butane, shown r, there is another compound, isobutane, which also has the formula C4 H10 .HHHHCCCHCHHHHHButane and isobutane are called structural isomers; they have the same formula but theatoms are connected in a different way. The number of isomers increases rapidly; C25 H52 hasover one million isomers.We can relate the isomers of Cn H2n 2 to graphs. Because of the physical properties of theatoms, each carbon atom must be bonded to 4 other atoms (chemists say carbon has “valency”4) and each hydrogen atom to 1 other atom, and the whole molecule must be connected.So we have a connected graph with n vertices of degree 4 and 2n 2 vertices of degree 1, so2e 4n (2n 2) and so e 3n 1, which is one less than the number of vertices. Consequentlythe graph is a tree.All the hydrogen atoms are leaves; if we remove them the remaining carbon vertices mustform a smaller tree. So if we want to know how many isomers there are, we need to count thenumber of non-isomorphic trees on n vertices, with no vertex having degree higher than 4.Example 3.4. How many isomers of pentane (C5 H12 ) are there?Exercise 3.5. How many isomers of hexane (C6 H14 ) are there?We might also consider compounds which have some other atoms. Chlorine (Cl) has valency1, oxygen (O) has valency 2, and nitrogen (N) has valency 3. We can again work out if thegraph is a tree, and draw the trees with the appropriate number of vertices, but a tree willtypically give more than one isomer since we will need to decide which vertex is the nitrogenatom, say.Example 3.6. Does C3 H8 O form a tree? How many isomers does it have?3–3BracingsSee the first homework sheet.6

3–4MazesA maze can be regarded as a graph where the edges are open passages and the vertices arelocations, with special “start” and “end” vertices. Often they are based on a square grid, withedges removed if they are blocked by walls, hedges, etc. So we start from a graph as on the leftof the diagram and remove some edges to get a subgraph such as the maze on the right.A maze is called “perfect” if every point in the maze can be reached from any other andif the path between any two points is unique. The maze above is perfect. These conditionsare equivalent to the maze being a spanning tree of the original grid graph. Random mazegeneration algorithms typically exploit this fact; there is an algorithm to generate a perfectmaze which is a randomised version of Kruskal’s algorithm, for example.Since a perfect maze is a spanning tree, if the original grid was n m there will be nmvertices and so nm 1 edges.Example 3.7. Find and prove a relationship between the numbers of dead ends (including,possibly, the start and end vertices), T-junctions and crossroads in a perfect maze resultingfrom a rectangular grid.3–5Electrical networksThe diagram gives a simple electrical network. A voltage X is applied across the battery,and currents i0 , . . . , i5 flow in the wires (where a negative current simply means a currentflowing in the other direction). The resistances R1 , . . . , R5 are known and we wish to work outthe currents.We have the following laws of electrical networks to help us.0. Going across the battery in the positive direction produces a voltage increase of X, i.e. avoltage drop of X.1. Ohm’s law. The voltage drop if a current i flows through a resistor of resistance R is iR.7

2. Kirchoff’s first law. The sum of currents entering a node is equal to the sum of currentsleaving it. This gives us four equations. However, these equations are not linearly independent and any one of them may be deduced from the other three. So we have threeequations (in six unknowns).3. Kirchoff’s second law. The sum of voltage drops around any cycle is 0. Together withOhm’s law this gives us several additional equations – one for each cycle.To avoid redundancy in Kirchoff’s second law we should take a system of fundamental cycles;this will produce linearly independent equations. Any spanning tree will have three fundamentalcycles, so gives us three more equations for a total of six linearly independent equations in sixunknowns. These will have a unique solution. In general if there are n vertices and e edgeswe have n 1 equations from the first law and e (n 1) fundamental cycles, so a total of eequations.Example 3.8. Pick a spanning tree and write down six linearly independent equations for thecircuit shown. Solve them when X 240 V, R1 R2 R3 R4 20 Ω and R5 30 Ω.44–1Eulerian graphsEuler trailsIs it possible to draw the graph shown without lifting thepen from the paper, or going over the same line twice?Recall that a walk is a route round the edges and vertices of a graph, and a trail is a walk inwhich the edges used are distinct. A trail (or walk) is closed if it starts and ends at the samevertex. A closed trail is not necessarily a cycle, since it may visit the same vertex several times.Definition 4.1. A graph is Eulerian if it has a closed trail which includes every edge. A graphis semi-Eulerian if has a trail which is not closed but which includes every edge.We refer to a closed trail which includes every edge as an Euler trail. Euler observed that,provided the graph is connected, we can tell whether it is Eulerian, semi-Eulerian, or neitherjust by looking at the degrees of the vertices. It is easy to see that an Eulerian graph must haveall its degrees even, but harder to show that a connected graph which satisfies this property isindeed Eulerian.Lemma 4.2. If G is a graph with all vertices having even degree, then the edges of G may bepartitioned into disjoint cycles.We will prove this in lecturesNext we show that for a connected graph we can stitch together these cycles into an Euler trail.Theorem 4.3 (Euler). A connected graph G is Eulerian if and only if every vertex has evendegree.8

We will prove this in lecturesWe get an equivalent condition for semi-Eulerian graphs by observing that a graph is semiEulerian if and only if we make it Eulerian by adding a single edge.Theorem 4.4 (Euler). A connected graph G is semi-Eulerian if and only if exactly two verticeshave odd degree.We will prove this in lecturesFleury’s algorithm finds an Euler trail in an Eulerian graph, or a trail which uses every edge ina semi-Eulerian graph.Definition 4.5. A bridge in a connected graph is an edge whose removal will disconnectthe graph. In an unconnected graph, a bridge is an edge whose removal will disconnect thecomponent it is in.Fleury’s algorithm proceeds as follows. If the graph is Eulerian, start at any vertex andmove along any edge, deleting that edge once you have crossed it, but only crossing a bridgeif there is no alternative. If it is semi-Eulerian, start at either vertex of odd degree and thenapply the same algorithm.4–2The Chinese Postman problemA postman delivers letters to a set of streets which form the edges of a connected graph G; thevertices of G are junctions between streets. He knows the length of each street (different streetsmay have different lengths). He needs to start and finish at the same junction, and travel alonga walk which covers every street at least once. What is the shortest walk he can take whichachieves this?The problem was originally studied by Mei-Ko Kwan (1962), who gave a necessary andsufficient condition for a shortest route. Edmonds and Johnson subsequently (1973) gave anefficient algorithm for finding the optimal closed walk.The postman can certainly do no better than the total length L of all the streets, and aroute of this length is precisely an Euler trail so he can do this if and only if G is Eulerian. Ifit is not Eulerian he will need to travel along some streets more than once.Theorem 4.6. If the graph is semi-Eulerian, x and y are the two vertices of odd degree, andthe shortest path between x and y has length P then the shortest postman route has lengthL P.Proof. The postman can certainly achieve this, by walking along a trail from x to y which coversevery edge and then back to x along a shortest path.To show that he can do no better, it is sufficient to show that in any closed walk whichcovers every edge, the set of edges covered twice include a path from x to y. We will completethe proof in lectures.We shall see an efficient algorithm to find the shortest path in a later lecture. The generalcase, where G may have several vertices of odd degree, is much harder.9

5Hamilton cyclesRecall that a cycle in a given graph is a subgraph isomorphic to Cn for some n, and a path in agraph is a subgraph isomorphic to Pm for some m (or, equivalently, a walk in which no vertexappears more than once).Definition 5.1. A Hamilton cycle in a graph is a cycle which includes every vertex, and aHamilton path is a path which includes every vertex.Definition 5.2. A graph is Hamiltonian if it has a Hamilton cycle, and semi-Hamiltonianif it is not Hamiltonian but does have a Hamilton path.In paths and cycles all the vertices have to be distinct (unlike trails where only edges have tobe distinct). So a Hamilton path or cycle visits every vertex exactly once; an Eulerian trail usesevery edge exactly once. It is much harder to determine whether a given graph is Hamiltonianthan whether it is Eulerian.Some examples of Hamiltonian graphs are the complete graph Kn (for n 3) and thecomplete bipartite graph Kn,n (for n 2), all five platonic graphs, and (harder) the “knight’sgraph” whose vertices are the squares of a chessboard and whose edges connect pairs of verticeswhich are a knight’s move apart.Exercise 5.3. Verify that the dodecahedron and icosahedron are Hamiltonian.Some examples of graphs which are not Hamiltonian are the complete bipartite graph Kn,mfor n 6 m (since any cycle in a bipartite graph must alternate between red and blue vertices,so must have the same number of each) and any graph with a bridge (since once we cross thebridge we can’t get back).There is no simple if-and-only-if condition for a graph to be Hamiltonian. There are somesufficient conditions, most of which say that a graph with plenty of edges everywhere is Hamiltonian. The first of these was proved by G. A. Dirac (1952).Theorem 5.4 (Dirac). If G is a simple graph with n 3 vertices and minimum degree at leastn2 then G is Hamiltonian.We will not give Dirac’s original proof, but instead deduce Dirac’s theorem from the subsequent result proved by Ore (1960).Theorem 5.5 (Ore). Let G be a simple graph with n 3 vertices. Suppose that every pairof distinct non-adjacent vertices (u, v) satisfies the inequality d(u) d(v) n. Then G isHamiltonian.Proof. Outline; we will fill in the details in lectures.1. Suppose G is not Hamiltonian. We may assume G is semi-Hamiltonian (why?).2. Take a Hamilton path v1 · · · vn , and imagine it running from left to right. Show that thereis some edge on the path whose right-hand vertex is adjacent to v1 and whose left-handvertex is adjacent to vn .3. Show how we may form a Hamilton cycle given such an edge.Example 5.6. What is the smallest number of edges that will ensure that a simple graph on10 vertices is Hamiltonian?10

We can deduce Dirac’s theorem immediately from Ore’s theorem: if d(v) n2 for every vthen d(u) d(v) n for every pair of vertices, so G is Hamiltonian. The n2 in Dirac’s theoremis best possible.Exercise 5.7. Any graph can be categorised as Eulerian (E), semi-Eulerian (SE), or neither(NE) and also as Hamiltonian (H), semi-Hamiltonian (SH), or neither (NH). Combining thesegives 9 categories of graphs; draw a simple connected example for each.6The Travelling Salesman problemA travelling salesman needs to visit each of a group of cities, returning to his starting point. Thedistance from each city to each other is known, and he wishes to minimise his total distance.This corresponds to finding a Hamilton cycle of minimum weight in a weighted complete graph.This is a hard problem. There are (n 1)! Hamilton cycles to choose from, and the factorialsgrow quite quickly. When n 10 we have 9! 362880; when n 20 we have 19! 1017 ; andwhen n 71 we have 70! 10100 .Suppose we have 5 towns with distances given by the following table.A15 B16 12 C6 19 5 D20 8 14 7 ESince we only have a few towns we could just list all the routes. But is there a quicker wayto get bounds on the minimum distance? Just picking any route, say ABCDE, gives us anupper bound, in this case 15 12 5 7 20 59. But this might not be very good; howmight we go about picking a route which is likely to give a good bound?The following is a heuristic algorithm for finding an upper bound, based on the principle ofnearest insertion. At each stage we have a cycle through some set of vertices which we expectto be reasonably short, and we insert another vertex to increase the length of the cycle, doingthis until we have a cycle through all the vertices.1. List the edges in increasing order of weight.2. Start with a single vertex, A, say, and find the shortest edge from A to another vertex.3. Start from the cycle of length 2 which goes along that edge and back again.4. Find the shortest edge from a vertex already in the cycle to a vertex not yet in the cycle.5. Add that edge to the cycle by inserting the new vertex after the vertex which was alreadyin the cycle.6. Repeat steps 4 and 5 until the cycle goes through all the vertices.Example 6.1. Carry this out for the distance table above, starting at A.Finding a lower bound is not as simple as finding an upper bound, since we have to be able toprove that every Hamilton cycle is at least as long. The following algorithm gives a reasonablelower bound.1. Pick a vertex, say A, and remove it.11

2. Use Kruskal’s algorithm to find a minimum spanning tree for the remainder.3. Find the two shortest edges from A to the rest of the graph.4. Add these two lengths to the total length of the spanning tree to get a lower bound.Lemma 6.2. This gives a lower bound on the travelling salesman problem.We will prove this in lecturesExample 6.3. Find a lower bound for the distance table above, removing A.In both cases the bound we get will depend on the choice of vertex we make at the start.7Directed graphs and directed Hamilton pathsA directed graph, or digraph, is like a graph, but instead of a set of edges between pairsof vertices we have a set of arcs, where each arc goes from one vertex to another (or back toitself). We draw arcs as arrows. We might think of these as a system of one-way streets. If wewanted to represent a 2-way street we would do this by having an arc from a to b and anotherarc from b to a.A directed path in a directed graph is a sequence of arcs of the form v1 v2 , v2 v3 , . . . ,vk 1 vk , where the vi are distinct vertices. In other words it corresponds to our previousnotion of a path but all the arcs must be going in the right direction. A directed cycle is likewisea sequence v1 v2 , v2 v3 , . . . , vk 1 vk , vk v1 .Consider the following puzzle. Points a to g are arranged around a circle clockwise. From a,d or f we are allowed to move exactly 3 spaces either clockwise or anticlockwise (so from a wecould go to d or e); from b or e we are allowed to move 2 spaces in either direction; and from cor g we are allowed to move one space in either direction. Can we move around following theserules and visit every point exactly once?This is asking for a Hamilton path in a directed graph obtained by drawing arcs a dand a e, b g and b d, and so on. There is no efficient algorithm, but we might try tosystematically search for a solution either by breadth-first or depth-first searching.7–1Depth-first searchChoose a vertex to start from, a, say. Next choose any unvisited vertex reachable from a, andgo there. Keep going, at every stage choosing an unvisited vertex which we are allowed to moveto – mark any vertex from which we have only one option. Keep going until you either find aHamilton path or are stuck – when you are stuck backtrack to the previous vertex where therewas a choice and choose differently.Example 7.1. Find a solution to the puzzle above using depth-first search.7–2Breadth-first searchWe aim to build up a tree of possible routes. Start with a in the first column, then put thepossible vertices you can get to from a in the next column, then the possible ways to continuethese paths in the third column, and so on. We will find all possibilities this way.Example 7.2. Find all solutions to the puzzle above using breadth-first search.12

Exercise 7.3. Arrange points a to k in a circle clockwise. From g or j you may move one stepin either direction; from d or f exactly two steps in either direction; from b, e or h you maymove exactly three steps in either direction; from a, c or k, four; and from i, five. Find a routethrough all the vertices starting at a.8Shortest and longest paths8–1Shortest pathsRecall that a weighted graph (or digraph) is one where each edge (or arc) has a positive “weight”,which we typically think of as representing distance, time or cost of travel, associated with it. Itis natural to ask for the shortest (in terms of total weight) path between two points in a graphor digraph; we have already seen an application of this in the Chinese Postman problem. Howmight we go about finding the shortest path from A to L in the following weighted graph?2B348A259H19FJ52E6G16C2D62I2L3KDijkstra’s algorithm finds the shortest distance to every vertex. We will not give a formalproof that it works. At each step of the algorithm there will be some vertices marked withdistances, and we need to distinguish which are final answers and which are merely bounds(which may change). We typically do this by circling the final answers.1. Start by marking the start vertex as distance 0, and circle it.2. For each vertex adjacent to the start vertex, we calculate a bound which is the length ofthe edge to that vertex.3. Find the vertex with the smallest bound among vertices which do not have final answerscircled. Circle that bound, and mark the edge which gave that bound.4. For each

De nition 2.3. A path is a walk in which no vertex appears more than once. We might want to know whether there is a path (or trail, or walk) between speci c vertices xand y. First we note that the answer is the same in each case. Lemma 2.4. The following are equivalent: 1. there is a path from xto y; 2. there is a trail from xto y;