Graph Theory Exam - Foredragsnoter Alle PDF

Preview

Summary

Graph Theory ExamGRAPHTHEORY, 01227AUTHORCHRISTOPHERKADOW S 164184TECHNICALUNIVERSITY OFDENMARK(DTU)CONTENTS 1 Pensum in the different weeks CONTENTS 2 Week 3 Week 3 Dijkstra’s algorithm 3 Number of shortest paths 4 Week 4 Kruskal’s algorithm 4 Euler tours 4 Chinese postman problem 5 Week 5 Matching...

Description

Graph Theory Exam G RAPH T HEORY, 01227

A UTHOR

C HRISTOPH ER KADOW S 164184

T ECHNICAL U NIVERSITY

OF

DENMARK (DTU)

CONTENTS

CONTENTS 1 Pensum in the different weeks

2

2 Week 1

5

3 Week 2 3.1 Dijkstra’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Number of shortest paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 6 6

4 Week 3 4.1 Kruskal’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Euler tours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Chinese postman problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 7 7 7

5 Week 4 5.1 Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Covering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Augmenting paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Hungarian algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Hungarian algorithm in bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 Perfect matching in a bipartite graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.7 Application: Carving out dominos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.8 Application: Structure rank of a matrix . . . . . . . . . . . . . . . . . . . . . . . . . .

9 9 9 9 10 10 10 11 11

6 Week 5 12 6.1 Benzenoids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.2 Finding the Pauling bonds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 7 Week 6 13 7.1 Job assignment problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 7.2 Teacher class problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 8 Week 7 8.1 Flow definitions . . . . . . . . . . . 8.2 Maximum flows and minimum cuts 8.3 Finding a minimum s − t cut . . . 8.4 Finding a maximum flow . . . . . . 8.5 Known from exercises . . . . . . .

. . . . .

15 15 15 15 16 17

9 Week 8 9.1 Finding a minimum cut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2 Find optimal edges from white to white . . . . . . . . . . . . . . . . . . . . . . . . . 9.3 Known from exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18 18 19 19

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

10 Week 9 10.1 Connectivity and edge-connectivity 10.2 Counting spanning trees . . . . . . 10.3 Contraction-Deletion . . . . . . . . 10.4 Complete graphs . . . . . . . . . . 10.5 Matrix tree theorem . . . . . . . . 10.6 Known from exercises . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

20 20 20 20 21 21 22

11 Week 10 23 11.1 Fundamental cuts and cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 11.2 Cut matrix and cycle matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 12 Week 11 12.1 Co-tree product . . . . . 12.2 Network determinant . . 12.3 Kirchhoff’s rule . . . . . 12.4 Driving point resistance

. . . .

26 26 26 27 27

13 Week 12 13.1 Vertex voltages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.2 Random walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.3 Computing node voltages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28 28 28 29

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

14 Week 13 30 14.1 General definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 14.2 Kuratowski’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

1

1 PENSUM IN THE DIFFERENT WEEKS This is a short summary of what we should know each week. This is to keep an overview, and to know where one should look up the different things. Remember: It is always easy to find a summary of a week by looking at the week plan for the next week.

Week 1 • What is a graph? (FN chapter 1, section 1-6) • What does it mean two graphs are isomorphic? • What does it mean a graph is connected? • What is a (spanning)tree? • What is a bridge? • What is a cut vertex? • What are the distance classes for a vertex? • What is a bipartite graph?

Week 2 • Dijkstra’s algorithm (shortest paths) (BM 15-21) (FN 4.1-4.6) • Complexity of algorithms (BM p. 19) (FN section 11) • Sorting a graph (FN section 15 - not so deep)

Week 3 • Kruskal’s algorithm (and Prim’s) (BM 36-41) (FN section 30) • Chinese Postman Problem (BM 62-65) (FN section 34)

Week 4 • Matchings (BM chapter 5) (FN section 26 without proofs) • Structure rank

2

1. PENSUM IN THE DIFFERENT WEEKS • The Hungarian algorithm

Week 5 • Matchings and Benezoids (BM 139-141) (FN 1.31) • Pauling bonds • Katacondensated Benezoids (those are what we will be working with)

Week 6 • Matchings and job assignment problem (BM Chapter 5 and 6.3) • Time table problem • The plotter problem • Konig’s theorem

Week 7 • Network flows (FN 3.1-3.29 expect section 20 and 3.18-3.19) • Capacity of cuts

Week 8 • Critical and optimal edges (FN 3.42-3.45) (Aslo week plan 8) • Menger’s theorems (BM 203-205) (FN section 27)

Week 9 • Connectivity and edge-connectivity • Counting spanning trees (BM 212-219) (FN section 36 and 37)

Week 10 • Tellegen’s theorem (FN section 38, 39 and 40) • Cut matrix and cycle matrix • Fundamental cuts and cycles • Algorithm to find minimum s-t cut containing edge k 3

1. PENSUM IN THE DIFFERENT WEEKS

Week 11 • Kirchoff’s rule (FN chapter 6) • Driving point resistance (effective resistance)

Week 12 • Vertex voltages (node voltages) (Week plan) (FN last page chapter 5) • Random walks (Markov chains, Brownian motions)

Week 13 • Eulers formula for planar graphs (BM 9.1-9.3) • Kuratowski’s theorem • Block (BM 3.1-3.2) Remark: Most of the work should be in understanding week 10-12, since those are definitely the hardest topics.

4

2 WEEK 1 A graph G is a set of vertices V and a set of edges E. v is the number of vertices and e is the number of edges. A directed graph is a graph where the edges have arrows. Edges connect the vertices. A connected graph where for each vertex we can get to all the others going through edges. Two graphs are isomorphic if they are essentially the same. That is, can we move the vertices around such that the two graphs are equal. The easiest way is to find out if two graphs are not isomorphic. Find a property one graph has which the other does not - then they cannot be isomorphic. There is not algorithm to quickly determine if two graphs are isomorphic or not. A tree is a graph with no cycles and where all vertices are connected (if they are not connected and no cycles, then it is a forest). If we have a connected graph we can make a spanning tree on top of that, that touches all the vertices but does not contain cycles. A bridge is an edge where if we remove it, we go from having one connected graph to have two connected graphs. A cut vertex is a vertex with the same property as the bridge, but we look at removing a vertex instead. If we focus on one vertex v1 in a graph we can find the distance classes to all the others in a connected graph. All the vertices which are only one edge away from v1 is in distance class one. If we have to go over two edges to get to a vertex, then that vertex is in distance class two and so on. v1 is in distance class 0. A bipartite graph is a graph such that we split the vertices up into two disjoint sets. That is, that one set contains vertices that are not connected by one edge and the other set likewise. A graph that contains no odd-length cycles are bipartite. If the graph is not connected there are more possibilities in splitting the graph up.

5

3 WEEK 2 3.1

Dijkstra’s algorithm

Let w(u,v) denote the weight of the edge vu. Let s denote a starting vertex, and let l(u) denote the distance from s to u. Start by assigning all distances to ∞ (except s, since it has distance 0). We mark s as it has been visited. Then do: Algorithm 1 Dijkstra’s algorithm max = 0 for all vertices do for all neighbors u of v do if l(v) + w(v,u) < l(u) then l(u) = l(v) + w(v,u) end if end for Mark v as visited end for This way you will always find the shortest path to each vertex, which has been proven in the course. If a graph is directed, instead of looking at all neighbors just look at the neighbors going directly from u. When all the distances are found, it is easy to find the actual paths - just found the way that matches the distance.

3.2

Number of shortest paths

If you calculate the distance class of each one. The number of shortest paths are the number of neighbors a vertex has with a distance class one less than the vertex you are looking at. One can use Dijkstra’s algorithm to find number of shortest paths for a weighted graph. Remark: Complexity of algorithms is known from other courses, and is not that important in this. Therefore, we will not go into this here. Remark 2: In this week the girth of a graph is also introduced, which is the length of the shortest cycle. Remark 3: This week also talks about degree sequence. Look in David-Hjalte.

6

4 WEEK 3 4.1

Kruskal’s algorithm

Kruskal’s algorithm is a very simple greedy algorithm. It works like the following: Algorithm 2 Kruskal’s algorithm label the edges in non-decreasing order of weight e1 , . . . , em for i = 1 . . . m do Mark ei unless it creates a cycle of marked edges end for When the algorithm terminates, the output will be a minimum spanning tree. Prim’s algorithm is very similar, and does the same.

4.2

Euler tours

An Euler tour is a tour where we start and end in the same spot and we go over every edge. If the graph has an Euler tour, it is eulerian. A graph is only eulerian iff is connected and all vertices have even degree. An Euler trail is if we do not start and end in the same spot. A graph has an Euler trail iff it is connected and exactly two vertices have odd degree, and the rest even.

4.3

Chinese postman problem

The chinese postman problem is about a postman that has to deliver mail to all houses, which means he has to walk down every street (edges). If the graph has an euler tour, that would of course be the shortest, but most of the time he has to walk down an edge twice. If he walks down one twice, we can see it as doubling the edge, and we call the new edge a waste edge. All waste edges are contained in the graph W , and G + W will then be eulerian. If we find a waste graph W of minimum weight, we can solce the problem. The algorithm Start by having a weighted graph G with a starting vertex s. Then start by marking all vertices of odd degree (there will always be an even number of those). Then make an auxiliary graph (see DH page 20-21). This is a graph where all the odd-degree vertices are connected, and the weight to go from one to another is the edges. Find a minimum perfect mathcing of the auxiliary graph. That is a graph with a perfect matching containing minimum possible weight. Then the edges in G corresponding to the edges marked in

7

4. WEEK 3 the matching of the auxiliary graph should be doubled, and then G is eularian and the problem is solved. If we want to end in distinct places one can do the same, making sure that the starting vertex and the end vertex have odd degree, thereby adding them to the waste graph if they have even degree.

8

5 WEEK 4 5.1

Matchings

A matching is a set of edges such that no edges are incident to each other in the graph. If a vertex v is incident to an edge in the matching it is saturated by the matching. Otherwise unsaturated. Perfect matching A perfect matching is matching where all vertices are saturated. The number of vertices has to be even for this to be possible (not sufficient condition). Maximal and maximum matching A matching is maximal if it is not possible to add more edges in the matching. A maximum matching is a matching with as many edges as possible.

5.2

Covering

A covering C is a set of vertices such that every edge in the graph is adjacent to at least one vertex in C. That means if we remove all vertices in C from the graph the graph will contain no edges. The number of vertices in a covering is at least as big as the number of edges in a matching. If we find a matching where the edges are equal to the number of vertices in a covering, we know the matching is maximum and the covering is minimum. That is the way it should be proved that a matching found is maximum and the covering found is minimum. Though it is not always a graph contains a minimum covering and a maximum matching of same size. Bipartite graphs In bipartite graphs we can utilize König’s theorem which states that the number of edges in a maximum matching will always be equal to the number of vertices in a minimum covering.

5.3

Augmenting paths

M -Alternating path An M -alternating path in G is a path in G consisting of edges alternately in M and not in M . M -Augmenting path An M -augmenting path is a M -alternating path in G for which both end points are unsaturated by M .

9

5. WEEK 4

5.4

Hungarian algorithm

This algorithm is used to find a maximum matching. If we make a matching in G and find an augmenting path, we know we can swap the edges in the matching and those not in the matching around in the augmenting path, and hereby increase the matching by 1. This leads to Berge’s theorem: Theorem 5.1 (Berge’s theorem). A matching M in a graph G is maximum iff G contains no M augmenting paths. Therefore we can find the maximum matching by starting with a random matching and keep changing it until it contains no augmenting paths. Algorithm 3 Hungarian Algorithm find a maximal matching M in G while there exist an augmenting path in G do Find an M − augmenting path in G and increase the matching end while This works for all graphs but are especially good for bipartite graphs.

5.5

Hungarian algorithm in bipartite graphs

Recall a bipartite graph is written G = (A ∪ B, E), since the vertices can be split up in two sets. Now we will use the marking procedure. The marking procedure: Start by marking all unsaturated vertices in A squares. Then continue expanding the marking using these two rules repeatedly: 1. In every square: Follow all edges to B and mark the neighbors as triangles. 2. In every triangle: Follow the matched edge to A and mark that neighbor as a square. If at some point we mark a unsaturated vertex in B as a square, we have found an augmenting path and we can increase the matching. If the algorithm terminates without finding an augmenting path, then we know the matching is maximum. The unmarked vertices in A and the marked vertices in B are the vertices in the minimum covering.

5.6

Perfect matching in a bipartite graph

We have a bipartite graph G = (A ∪ B, E). We can use Hall’s theorem to know if there exist a perfect matching in the bipartite graph: Theorem 5.2 (Halls’ theorem). A bipartite graph G = (A ∪ B,E) has a matching that saturates all vertices in A iff every subset S of A has at least |S| neighbors in B . From this theorem we can derive two important corollaries:

10

5. WEEK 4 Corollary 5.3. A biparite graph G = (A ∪ B,E) has a perfect matching iff |A| = |B| and every subset S of A has at least |S| neighbors in B . Corollary 5.4. If G is k-regular (all vertices have degree k) and biparite, then G has a perfect matching.

5.7

Application: Carving out dominos

Suppose you have a wooden board with alternating black and white squares and your goal is to cut out domino bricks (as many as possible) containing a black and a white square. Then we can see the wooden board as a bipartite graph and finding a maximum matching is how many dominos you can cut out. Use the hungarian algorithm to find the maximum matching.

5.8

Application: Structure rank of a matrix

The structure rank of a (0,1)-matrix is the number of 1’s than can be selected without any of the selected being in the same row and the same column. Let every row correspond to the set A and let every column correspond to the set B. There is an edge between ai and bj if there is a 1 in A(i,j). If we can mark columns and rows such that the number of 1’s selcted is equal to the number of unmarked rows and the number of marked columns, we will have a maximum matching and thereby the struture rank.

11

6 WEEK 5 6.1

Benzenoids

A benzenoid is basically hexagons in chemical bonds. We are not interested in the chemistry, though, but it is compounds found in organical chemistry. It is benzene rings jointed together. We want to investigate the following for a benzenoid B : • Does B exist in nature? • If so, what are the bond orders between the individual carbon atomes in B ? It turns out that B can be realized in nature iff it has a perfect matching. For each edge xy we can then define the Pauling bonds: Definition 6.1. The Pauling bond of an edge xy is the number 1 + Pp(xy) , where p(xy) is the number (t) of perfect matchings in B containing xy and P (t) is the number of perfect matching in B .

6.2

Finding the Pauling bonds

There is a very fast method of finding the Pauling bonds if the dual graph of B is a tree T (that is probably the only thing we will be working ...