TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 33

Use a suitable graph model to reformulate the exercise as graph theoretical problem:

Given a subset $A\subseteq R^2$ which has area $a$ and two decomposition of $A$ into subsets $A_1,A_2\dots ,A_m$ and $B_1,B_2,\dots ,B_m$ such that all the $A_i$ ’s and all the $B_i$ ’s have the same area $a/m$. Prove that there exists a permutation $\pi$ of $1,2,\dots ,m$ such that for all $i=1,\dots ,m$ we have $A_i\cap B_{\pi }(i)\ne \varnothing$.

Solution

For every area $A_1,A_2,\dots ,A_m$ and $B_1,B_2,\dots ,B_m$ we draw a node. For every set $A_i$ and $B_j$ which share a common area ($A_i\cap B_j\ne \mathrm{\varnothing }$) we draw an undirected edge between their nodes. From this construction we get a bipartite graph. To show that there exists a permutation $\pi$ we need to find an edge matching where every node occurs exactly once (perfect matching). The Figure below shows an example for two compositions and a possible permutation $\pi$.

According to König's theorem the number of edges in a perfect matching equals the number of nodes in a minimum vertex cover. Since we need either all nodes $A_i$ or $B_i$ to get a minimum vertex cover (Why?? Example from Wikipedia: http://upload.wikimedia.org/wikipedia/commons/2/2e/Koenigs-theorem-graph.svg - not every vertex from A or B is used. The only thing I can come up with is, that every vertex is connected to at least one distinct vertex in B (when A = B, so all Ai = Bi) or have additional edges (when moving the areas a little bit, they will still overlap there Bi, but also other areas. But this would already be a proof for the whole thing. Any other ideas? — no nodes of either group are directly connected to each other — we need $m$ nodes to construct a minimal vertex cover. This means a perfect matching with $m$ edges exist. This matching gives us a correct permutation $\pi$ since each node in this edge matching must occur exactly once.

Scheint nicht ganz zu stimmen, siehe: https://math.stackexchange.com/questions/1511777/reformulating-a-problem-as-graph-theoretic

Alternative Solution (suggestion)

Using the graph model from above, let $L=A_1\cup \dots \cup A_m$ and $R=B_1\cup \dots \cup B_m$. Until now we have a model, and we know that for the permutation to exist, there must be a complete (i.e. perfect) matching in our graph. So we need to show that such a matching exists for all m. Now observe some properties of the graph:

• $|L|=|R|$, since both L and R are decompositions into m parts.
• Every $A_i$ is connected to at least one $B_j$ - Since both decompositions cover the whole area of A, the area covered by any one element of one decomposition must also be covered in the other decomposition.
• Because every element in L is connected to at least one element in R, we can state that $\mathrm{\forall }LP\subseteq L:|\Gamma (LP)|\ge |LP|$, i.e. the neighborhood of every set of elements on the left has at least as many elements as the set itself.

These are exactly the conditions under which a complete matching exists according to Hall's Marriage Theorem - which is known to be true ;) - so we're done here.

Materialien

Neues Material hinzufügen

E

• Exercise 33.png (details)