[ Pobierz całość w formacie PDF ]
tour, which proves the assertion above.
To sum up, the cost of the tour we constructed is at most twice that of the cheapest
spanning tree, which in turn is less than twice the cost of a cheapest tour.
11.5 Is the tour in figure 29 shortest possible?
11.6 Prove that if all costs are proportional to distances, then a shortest tour cannot
intersect itself.
97
Figure 29: The cheapest tree connecting 15 given towns, the walk around it, and the tour
produced by shortcuts. Costs are proportional to distances.
12 Matchings in graphs
12.1 A dancing problem
At the prom, 300 students took part. They did not all know each other; in fact, every
girl new exactly 50 boys and every boy new exactly 50 girls (we assume, as before, that
acquaintance is mutual).
We claim that they can all dance simultaneously (so that only pairs who know each
other dance with each other).
Since we are talking about acquaintances, it is natural to describe the situation by
a graph (or at least, imagine the graph that describes it). So we draw 300 nodes, each
representing a student, and connect two of them if they know each other. Actually, we can
make the graph a little simpler: the fact that two boys, or two girls, know each other plays
no role whatsoever in this problem: so we don t have to draw those edges that correspond
to such acquaintances. We can then arrange the nodes, conveniently, so that the nodes
representing boys are on the left, nodes representing girls are on the right; then every edge
will connect a node from the left to a node from the right. We shall denote the set of nodes
on the left by A, the set of nodes on the right by B.
This way we got a special kind of graph, called a bipartite graph. Figure 30 shows such
a graph (of course, depicting a smaller party). The thick edges show one way to pair up
people for dancing. Such a set of edges is called a perfect matching.
To be precise, let s give the definitions of these terms: a graph is bipartite if its nodes
can be partitioned into two classes, say A and B so that every edge connects a node in A
98
Figure 30: A bipartite graph and a perfect matching in it
to a node in B. A perfect matching is a set of edges such that every node is incident with
exactly one of them.
After this, we can formulate our problem in the language of graph theory as follows:
we have a bipartite graph with 300 nodes, in which every node has degree 50. We want to
prove that it contains a perfect matching.
As before, it is good idea to generalize the assertion to any number of nodes. Let s be
daring and guess that the numbers 300 and 50 play no role whatsoever. The only condition
that matters is that all nodes have the same degree (and this is not 0). Thus we set out to
prove the following theorem:
Theorem 12.1 If every node of a bipartite graph has the same degree d e" 1, then it
contains a perfect matching.
Before proving the theorem, it will be useful to solve some exercises, and discuss another
problem.
12.1 It is obvious that for a bipartite graph to contain a perfect matching, it is necessary
that |A| = |B|. Show that if every node has the same degree, then this is indeed so.
12.2 Show by examples that the conditions formulated in the theorem cannot be
dropped:
(a) A non-bipartite graph in which every node has the same degree need not contain a
perfect matching.
(b) A bipartite graph in which every node has positive degree (but not all the same)
need not contain a perfect matching.
12.3 Prove Theorem 12.1 for d = 1 and d =2.
99
3
2
1
C
B
A
E
D
F
5
6
4
border between tribes
border between tortoises
Figure 31: Six tribes and six tortoises on an island
12.2 Another matching problem
An island is inhabited by six tribes. They are on good terms and split up the island between
them, so that each tribe has a hunting territory of 100 square miles. The whole island has
an area of 600 miles.
The tribes decide that they all should choose new totems. They decide that each tribe
should pick one of the six species of tortoise that live on the island. Of course, they want
to pick different totems, and so that the totem fo each tribe should occur somewhere on
their territory. [ Pobierz całość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl aikidobyd.xlx.pl
tour, which proves the assertion above.
To sum up, the cost of the tour we constructed is at most twice that of the cheapest
spanning tree, which in turn is less than twice the cost of a cheapest tour.
11.5 Is the tour in figure 29 shortest possible?
11.6 Prove that if all costs are proportional to distances, then a shortest tour cannot
intersect itself.
97
Figure 29: The cheapest tree connecting 15 given towns, the walk around it, and the tour
produced by shortcuts. Costs are proportional to distances.
12 Matchings in graphs
12.1 A dancing problem
At the prom, 300 students took part. They did not all know each other; in fact, every
girl new exactly 50 boys and every boy new exactly 50 girls (we assume, as before, that
acquaintance is mutual).
We claim that they can all dance simultaneously (so that only pairs who know each
other dance with each other).
Since we are talking about acquaintances, it is natural to describe the situation by
a graph (or at least, imagine the graph that describes it). So we draw 300 nodes, each
representing a student, and connect two of them if they know each other. Actually, we can
make the graph a little simpler: the fact that two boys, or two girls, know each other plays
no role whatsoever in this problem: so we don t have to draw those edges that correspond
to such acquaintances. We can then arrange the nodes, conveniently, so that the nodes
representing boys are on the left, nodes representing girls are on the right; then every edge
will connect a node from the left to a node from the right. We shall denote the set of nodes
on the left by A, the set of nodes on the right by B.
This way we got a special kind of graph, called a bipartite graph. Figure 30 shows such
a graph (of course, depicting a smaller party). The thick edges show one way to pair up
people for dancing. Such a set of edges is called a perfect matching.
To be precise, let s give the definitions of these terms: a graph is bipartite if its nodes
can be partitioned into two classes, say A and B so that every edge connects a node in A
98
Figure 30: A bipartite graph and a perfect matching in it
to a node in B. A perfect matching is a set of edges such that every node is incident with
exactly one of them.
After this, we can formulate our problem in the language of graph theory as follows:
we have a bipartite graph with 300 nodes, in which every node has degree 50. We want to
prove that it contains a perfect matching.
As before, it is good idea to generalize the assertion to any number of nodes. Let s be
daring and guess that the numbers 300 and 50 play no role whatsoever. The only condition
that matters is that all nodes have the same degree (and this is not 0). Thus we set out to
prove the following theorem:
Theorem 12.1 If every node of a bipartite graph has the same degree d e" 1, then it
contains a perfect matching.
Before proving the theorem, it will be useful to solve some exercises, and discuss another
problem.
12.1 It is obvious that for a bipartite graph to contain a perfect matching, it is necessary
that |A| = |B|. Show that if every node has the same degree, then this is indeed so.
12.2 Show by examples that the conditions formulated in the theorem cannot be
dropped:
(a) A non-bipartite graph in which every node has the same degree need not contain a
perfect matching.
(b) A bipartite graph in which every node has positive degree (but not all the same)
need not contain a perfect matching.
12.3 Prove Theorem 12.1 for d = 1 and d =2.
99
3
2
1
C
B
A
E
D
F
5
6
4
border between tribes
border between tortoises
Figure 31: Six tribes and six tortoises on an island
12.2 Another matching problem
An island is inhabited by six tribes. They are on good terms and split up the island between
them, so that each tribe has a hunting territory of 100 square miles. The whole island has
an area of 600 miles.
The tribes decide that they all should choose new totems. They decide that each tribe
should pick one of the six species of tortoise that live on the island. Of course, they want
to pick different totems, and so that the totem fo each tribe should occur somewhere on
their territory. [ Pobierz całość w formacie PDF ]