A Study of graph decomposition problems

我们证明了如下定理：设$m$是一个正整数，设$T_1，点，T_q$是$q$不相交的有根树，使得$|T_i|\in m，m1，$v_i$是$T_i$的根。设$P$是平面上处于一般位置的$|T_1|\cdots|T_q|$点的集合，其中包含$q$指定点$p_1，\cdots，p_q$。则具有根$v_1，\cdots，v_q$的根林$T_1\cup\cdots\cup T_q$可以直线嵌入到$P$上，使得每个$v_i$对应于每一个$1\le q$对应的$p_i$。为了证明上面的定理，我们证明了下一个定理：设$m$是正整数，设$S_1$，$S_2$和$T_$是平面上三个不相交的点集，使得$S_1\杯S_2\杯T$的三个点不在同一条直线上且$|T|=(m-L)|S_1|m|S_2|$。设$Q=|S_1\杯S_2|$，则$S_1\杯S_2\杯T$可分成满足以下三个条件的$Q$不相交的子集$P_1，\cdots，P_q$：(I)${\rm\mbox{conv}}\，(P_J)=\Emptyset$对所有$1\leq i&lt；j\leq Q$；(Ii)S|P_i\CAP(S_1\CAP S_2)|=L$对所有$1\leq Q$；和(Iii)$|P_i\CAP T|=m-1$如果$|P_i\CAP S_1|=1$，$|P_i\CAP T|=m$如果$|P_i\CAP S_2|=-1$.我们证明给出了一个$0(n^4)$时间算法来寻找$n=|T_1|\cts|T_q|$阶根林的上述直线嵌入.

We prove the following theorem : Let $m$ be a positive integer, and let $T_1, \cdots, T_q$ be $q$ disjoint rooted trees such that $|T_ i| \in \ {m, m+1\} $ and $v_i$ is the root of $T_i$ for all $ 1\leq i\leq q$. Let $P$ be a set of $|T_1|+ \cdots +|T_q|$ points in the plane in general position that contains $q$ specified points $p_1, \cdots, p_q $. Then the rooted forest $ T_1 \cup \cdots \cup T_q$ with roots $v_1, \cdots, v_q$ can be straight-line embedded onto $P$ so that each $v_i$ corresponds to $p_i$ for every $1 \le i \le q$.In order to prove the theorem above, we prove the next theorem :Let $m$ be a positive integer and let $S_1$, $ S_2$ and $T$ be three disjoint sets of points in the plane such that no three points of $S_1 \cup S_2 \cup T$ lie on the same lineand $|T|=(m-l)|S_1|+ m|S_2|$. Put $q=|S_1 \cup S_2|$.Then $S_1 \cup S_2 \cup T$ can be partitioned into $q$ disjoint subsets $P_1, \cdots, P_q$ satisfying the following three conditions :(i) ${\rm \mbox {conv}} \, (P_i) \cap {\rm \mbox {conv}} \, (P_j)= \emptyset $ for all $1 \leq i<j \leq q$ ;(ii) S|P_i \cap (S_1 \cup S_2) |=l$ for all $1 \leq i \leq q$ ; and(iii) $|P_i \cap T|=m-1$ if $|P_i \cap S_1|=1$, and $|P_i \cap T|=m$ if $|P_i \cap S_2|=-1$.This partition is called a semi-balanced partition.Our proof gives an $0 (n^4) $ time algorithm for finding the above straight-line embedding of the rooted forest $ T_1\cup \cdots \cup T_q$ of order $n=|T_1|+ \cdots +|T_q|$.